ÃËÀÂÀ III. ÒÅÎÐÈß ÏÐÈÍßÒÈß ÐÅØÅÍÈÉ.
§11. Ìíîãîêðèòåðèàëüíàÿ îïòèìèçàöèÿ.
Â òåîðèè èãð îáû÷íî èíòåðåñóþòñÿ ñòðàòåãèÿìè, îïòèìàëüíûìè â íåêî-
òîðîì ñìûñëå äëÿ âñåõ èãðîêîâ. Íàïðèìåð, â èãðàõ ìíîãèõ ëèö ìû ðàñ-
ñìàòðèâàëè ñèòóàöèè ðàâíîâåñèÿ, óñòîé÷èâûå îòíîñèòåëüíî âîçìîæíûõ îò-
êëîíåíèé îäíîãî èãðîêà. Â äàííîé ãëàâå ïðåäïîëàãàåòñÿ, ÷òî èìååòñÿ îäíî
ëèöî, ïðèíèìàþùåå ðåøåíèå (ËÏÐ), âûáèðàþùåå ñòðàòåãèþ x   X. Ïðè
ýòîì âîçìîæíî íàëè÷èå íåîïðåäåëåííîñòåé. Òèïè÷íûì ïðèìåðîì íåîïðå-
äåëåííîñòè ÿâëÿåòñÿ ñòðàòåãèÿ âòîðîãî èãðîêà ïî îòíîøåíèþ ê ïåðâîìó
èãðîêó (ËÏÐ) â èãðå äâóõ ëèö. Çäåñü ó ïåðâîãî èãðîêà èìååòñÿ îäèí êðè-
òåðèé îöåíêè èñõîäîâ   åãî ôóíêöèÿ âûèãðûøà.
Â äàííîì ïàðàãðàôå ìû ðàññìîòðèì êàê áû ïðîòèâîïîëîæíûé ñëó÷àé:
èìååòñÿ îäíî ËÏÐ, íî ñòðàòåãèÿ x   X îöåíèâàåòñÿ íå ñêàëÿðíûì, à âåê-
òîðíûì êðèòåðèåì W (x) = (W1 (x), ..., Ws (x)). Ïðè ýòîì êàæäûé ÷àñòíûé
êðèòåðèé Wi (x) æåëàòåëüíî ìàêñèìèçèðîâàòü. Åñëè ïî ñìûñëó ýòîò êðèòå-
ðèé æåëàòåëüíî ìèíèìèçèðîâàòü, òî åãî ìîæíî çàìåíèòü íà  Wi (x). Èòàê,
íåîïðåäåëåííîñòü çäåñü âûðàæàåòñÿ íåÿñíîñòüþ öåëè ËÏÐ (íåñêîëüêî êðè-
òåðèåâ).
Çàäà÷à ìíîãîêðèòåðèàëüíîé îïòèìèçàöèè çàêëþ÷àåòñÿ â âûáîðå x   X
ïðè íàëè÷èè âåêòîðíîãî êðèòåðèÿ W (x). Êàêóþ ñòðàòåãèþ x   X ñëåäó-
åò âûáèðàòü ËÏÐ ? Îòâåò íà ýòîò âîïðîñ íå ïðîñò. Äåëî â òîì, ÷òî, êàê
ïðàâèëî, íå ñóùåñòâóåò ñòðàòåãèè x0   Arg max
 Wi (x), i = 1, ..., s.
x  X
Ïðèìåð. Ïóñòü X = {x1 , x2 , x3 , x4 }, s = 2 è âåêòîðíûå îöåíêè ñòðàòåãèé
ðàñïîëàãàþòñÿ íà ïëîñêîñòè (W1 , W2 ), êàê ýòî ïîêàçàíî íà ðèñóíêå.
TW2
aW (x1 )
 aW (x3 )
 aW (x4 )
aW (x2 )
E W1
Ðèñ. 11.1
Çäåñü Arg max
 W1 (x) = {x2 , x3 }, Arg max
 W2 (x) = {x1 }.
x  X
x  X
Ïðè ðåøåíèè ìíîãîêðèòåðèàëüíûõ çàäà÷ èñïîëüçóþò ñòðàòåãèè, îïòè-
ìàëüíûå ïî Ïàðåòî.
 1

Îïðåäåëåíèå. Ñòðàòåãèÿ x0   X íàçûâàåòñÿ îïòèìàëüíîé ïî Ïàðåòî,
åñëè íå ñóùåñòâóåò òàêîé ñòðàòåãèè x   X, ÷òî Wi (x)   Wi (x0 ), i = 1, ..., s,
è õîòÿ áû îäíî íåðàâåíñòâî âûïîëíåíî êàê ñòðîãîå, ò.å. W (x) = W (x0 ).
Ìíîæåñòâî âñåõ îïòèìàëüíûõ ïî Ïàðåòî ñòðàòåãèé îáîçíà÷èì ÷åðåç
P (X, W ). Â ðàññìîòðåííîì ïðèìåðå P (X, W) = {x1 , x3 }. Îòìåòèì ïðîñòîé
ñïîñîá ïðîâåðêè îïòèìàëüíîñòè ïî Ïàðåòî ñòðàòåãèè x. Ïóñòü Y = W (X)
  ìíîæåñòâî âåêòîðíûõ îöåíîê, îòâå÷àþùèõ âñåâîçìîæíûì ñòðàòåãèÿì
x   X. Ñäâèãàåì íåîòðèöàòåëüíûé îðòàíò Es
+ = {y   Es | yi   0, i = 1, ..., s}
åâêëèäîâà ïðîñòðàíñòâà Es â òî÷êó W(x). Åñëè ñäâèíóòûé îðòàíò (âêëþ÷àÿ
åãî ãðàíèöû) íå ñîäåðæèò äðóãèõ âåêòîðîâ, êðîìå W(x), òî x   P (X, W ).
Áîëåå ôîðìàëüíî óñëîâèå îïòèìàëüíîñòè ïî Ïàðåòî äëÿ ñòðàòåãèè x çàïè-
ñûâàåòñÿ â âèäå (W(x) + Es
+ )   Y = {W (x)}.
×àñòî èñïîëüçóþò áîëåå ñëàáîå îïðåäåëåíèå îïòèìàëüíîñòè.
Îïðåäåëåíèå. Ñòðàòåãèÿ x0   X íàçûâàåòñÿ îïòèìàëüíîé ïî Ñëåéòåðó,
åñëè íå ñóùåñòâóåò òàêîé ñòðàòåãèè x   X, ÷òî Wi (x) > Wi (x0 ), i = 1, ..., s.
Ìíîæåñòâî âñåõ îïòèìàëüíûõ ïî Ñëåéòåðó ñòðàòåãèé îáîçíà÷èì ÷åðåç
S(X, W ). Â ðàññìîòðåííîì ïðèìåðå S(X, W) = {x1 , x2 , x3 }. Îòìåòèì, ÷òî
ñòðàòåãèÿ x òîãäà è òîëüêî òîãäà ÿâëÿåòñÿ îïòèìàëüíîé ïî Ñëåéòåðó, êîãäà
ïîëîæèòåëüíûé îðòàíò, ñäâèíóòûé â òî÷êó W(x), íå ñîäåðæèò âíóòðè ñåáÿ
íèêàêèõ âåêòîðíûõ îöåíîê.
Èç îïðåäåëåíèé ñëåäóåò, ÷òî P (X, W )   S(X, W ). Â ïðèâåäåííîì ïðè-
ìåðå îïòèìàëüíûå ïî Ïàðåòî ñòðàòåãèè x1 , x3 íå ýêâèâàëåíòíû, òî åñòü
W (x1 ) = W (x3 ), è âîçíèêàåò ïðîáëåìà âûáîðà x   P (X, W ).
Ðàññìîòðèì îáëàñòè ïðèëîæåíèé ìíîãîêðèòåðèàëüíûõ çàäà÷. Ìû óæå
âñòðå÷àëèñü ñ îïòèìàëüíûìè ïî Ïàðåòî ñèòóàöèÿìè â èãðàõ ìíîãèõ ëèö.
Äðóãèå ïðèìåðû äàåò ýêîíîìèêà. Äåÿòåëüíîñòü ïðåäïðèÿòèÿ îöåíèâàåòñÿ
ïî íåñêîëüêèì ïîêàçàòåëÿì: ïðèáûëü, ñåáåñòîèìîñòü ïðîäóêöèè, âàëîâîé
âûïóñê è ò.ï. Àêòèâû áàíêà îöåíèâàþòñÿ îáû÷íî ïî äâóì ïîêàçàòåëÿì: äî-
õîäíîñòü è ðèñê. Åùå îäíà îáëàñòü ïðèëîæåíèé   ïðîåêòèðîâàíèå ñëîæ-
íûõ òåõíè÷åñêèõ îáúåêòîâ. Íàïðèìåð, êîíñòðóêöèÿ àâòîìîáèëÿ îöåíèâà-
åòñÿ ïî íåñêîëüêèì òåõíè÷åñêèì õàðàêòåðèñòèêàì: ñêîðîñòü, ãðóçîïîäúåì-
íîñòü, ýêîíîìè÷íîñòü äâèãàòåëÿ è ò.ä. Â êà÷åñòâå ïðîñòåéøåãî ïðèìåðà ðàñ-
ñìîòðèì çàäà÷ó ïðîåêòèðîâàíèÿ êîðîáêè.
Èìååòñÿ ïðÿìîóãîëüíèê èç ìåòàëëà ðàçìåðà a   b, a   b. Èç ÷åòûðåõ
óãëîâ ïðÿìîóãîëüíèêà âûðåçàþòñÿ êâàäðàòû ñî ñòîðîíîé x   X = [0, a/2)
2

è ìàòåðèàë ñãèáàåòñÿ âäîëü ëèíèé, îòìå÷åííûõ íà ðèñ. ïóíêòèðîì.
x x
Ðèñ. 11.2. Ðàçâåðòêà êîðîáêè.
Ïóñòü V (x) = x(a   2x)(b   2x)   îáúåì êîðîáêè, S(x) = 4x2   ñýêîíîì-
ëåííàÿ ïëîùàäü ïëàñòèíû. Îáà êðèòåðèÿ æåëàòåëüíî ìàêñèìèçèðîâàòü.
Êðèòåðèé V (x) âîçðàñòàåò íà îòðåçêå [0, x ] è óáûâàåò íà ïîëóèíòåðâàëå
[x  , a/2), ãäå
 x  = a + b  va2   ab + b2
6 .
Ñëåäîâàòåëüíî, P (X, W ) = [x , a/2).
Ðåøåíèå ìíîãîêðèòåðèàëüíîé çàäà÷è áóäåì ïîíèìàòü â ñëåäóþùåì ñìûñ-
ëå. Ñíà÷àëà íàõîäèì ìíîæåñòâî P (X, W) èëè S(X, W ). Çàòåì èñïîëüçóåòñÿ
êàêîé-ëèáî ìåòîä ñóæåíèÿ ýòèõ ìíîæåñòâ, ò.å. âûäåëÿþòñÿ ïîäìíîæåñòâà
P   P(X, W ) èëè S   S(X, W ). Îêîí÷àòåëüíûé âûáîð ñòðàòåãèè èç P
èëè S ïðîèçâîäèò ËÏÐ.
Âîçíèêàåò âîïðîñ: êîãäà ìíîæåñòâî P(X, W ) íå ïóñòî?
Òåîðåìà 3.1. Ïóñòü X   êîìïàêò ìåòðè÷åñêîãî ïðîñòðàíñòâà, à ÷àñò-
íûå êðèòåðèè Wi (x), i = 1, ..., s, íåïðåðûâíû íà X. Òîãäà ìíîæåñòâî P (X, W)
íå ïóñòî.
Äîêàçàòåëüñòâî. Ðàññìîòðèì ñëåäóþùóþ ñâåðòêó âåêòîðíîãî êðèòåðèÿ:
  i Wi (x),
F1 ( , x) = s
i= 1
 s
  = ( 1 , ...,  s )     = {  |
  i = 1,  i > 0, i = 1, ..., s}.
i =1
= Arg max
 F1 ( , x)   P(X, W ). Çàìåòèì, ÷òî ìíîæåñòâî
Ïîêàæåì, ÷òî X1 ( )def
x  X
X1 ( ) íå ïóñòî, ïîñêîëüêó ôóíêöèÿ F1 ( , x) íåïðåðûâíà íà êîìïàêòå X.
Ïðåäïîëîæèì ïðîòèâíîå, òî åñòü   x   X1 ( )\P (X, W ). Òîãäà   x   X :
Wi (x)   Wi (x ), i = 1, ..., s è W (x) = W (x ). Äîìíîæèì êàæäîå íåðàâåíñòâî
3

  i Wi (x). Ýòî
íà  i > 0 è ñëîæèì èõ. Â ðåçóëüòàòå ïîëó÷èì s
  i Wi (x) > s
i =1
i =1
ïðîòèâîðå÷èò òîìó, ÷òî x   X1 ( ).
Òàêèì îáðàçîì, ìàêñèìèçèðóÿ ñâåðòêó F1 ( , x), ìîæíî ïîëó÷àòü îïòè-
ìàëüíûå ïî Ïàðåòî ñòðàòåãèè. Íî äëÿ âñÿêîãî ëè x   P(X, W )        : x  
X1 ( )? Îòâåò â îáùåì ñëó÷àå îòðèöàòåëüíûé.
Ïðèìåð. Ïóñòü s = 2, x = (x1 , x2 ) = W(x). Ìíîæåñòâî X   íåâûïóêëûé
÷åòûðåõóãîëüíèê OABC   èçîáðàæåíî íà ðèñóíêå.
TW2 = x2
e
A
e
e
e
e
ee
 B
r
r
r
X
r
r
r
 r
 E W1 = x1
 C
O
Çäåñü ëîìàíàÿ ABC   ìíîæåñòâî P (X, W ). Ïðè ïîëîæèòåëüíûõ  1 ,  2
ìíîæåñòâî X1 ( ) ñîäåðæèòñÿ â äâóõòî÷å÷íîì ìíîæåñòâå {A, C}.
Ðàññìîòðèì äðóãóþ ñâåðòêó F2 ( , x) = min
  i Wi (x), ãäå      . Ïðè èñ-
1  i  s
ïîëüçîâàíèè ýòîé ñâåðòêè áóäåì ïðåäïîëàãàòü, ÷òî Wi (x) > 0,  x   X, i =
1, ..., s. Ýòî íå ÿâëÿåòñÿ îãðàíè÷åíèåì îáùíîñòè.
Óïðàæíåíèå. Äîêàæèòå, ÷òî åñëè êî âñåì ÷àñòíûì êðèòåðèÿì äîáàâèòü
ïîëîæèòåëüíûå êîíñòàíòû, òî ìíîæåñòâî P (X, W ) íå èçìåíèòñÿ.
Òåîðåìà 3.2.(Þ.Á.Ãåðìåéåð). Ïóñòü âñå ÷àñòíûå êðèòåðèè Wi (x) íåïðå-
ðûâíû è ïîëîæèòåëüíû íà êîìïàêòå X ìåòðè÷åñêîãî ïðîñòðàíñòâà. Òîãäà
 (1)
S(X, W) =       X2 ( ).
Äîêàçàòåëüñòâî. Ïóñòü      . Äîêàæåì, ÷òî X2 ( )   S(X, W ). Ïðåäïîëî-
æèì, ÷òî   x   X2 ( )\S(X, W ). Òîãäà   x   X : Wi (x) > Wi (x ), i = 1, ..., s.
Îòñþäà min
  i Wi (x) > min
  i Wi (x ). Ýòî ïðîòèâîðå÷èò òîìó, ÷òî x  
1  i  s
1   i  s
X2 ( ). Èòàê, äîêàçàíî, ÷òî ïðàâàÿ ÷àñòü (1) ñîäåðæèòñÿ â ëåâîé.
Îáðàòíî. Ïóñòü x0   S(X, W ). Íàéäåì  0     : x0   X2 ( 0 ). Ïîëîæèì
 , i = 1, ..., s.
 0
i = 1
 1
Wi (x0 ) s
Wk ( x0 )
k =1
  1 . Ïóñòü x   X, x = x0 .
Òîãäà F2 ( 0 , x0 ) = min
 1
  0
i Wi (x0 ) = s
Wk (x0 )
1   i  s
k =1
4

Òîãäà   i1 : Wi 1 (x)   Wi 1 (x0 ). Èìååì
F2 ( 0 , x) = min
  0
i 1 Wi1 (x0 ) =
i Wi (x)    0
i1 Wi 1 (x)    0
1   i  s
  1
 s
 1
=
 = F2 ( 0 , x0 ).
Wk (x0 )
k =1
Îòñþäà ñëåäóåò, ÷òî x0   X2 ( 0 ).
Ê ñîæàëåíèþ, íå âñåãäà X2 ( )   P (X, W ).
Ïðèìåð. Êàê è â ïðåäûäóùåì ïðèìåðå, ïîëîæèì W(x) = x = (x1 , x2 )  
X = [0, 1]2 . Çäåñü
F2 ( , x) = min[ 1 x1 ,  2 x2 ], P (X, W ) = {(1, 1)}.
Ðàññìîòðèì ëèíèþ óðîâíÿ ôóíêöèè F2 ( , x)   ìíîæåñòâî âèäà {x | F2 ( , x) =
C}. Íà ðèñóíêå èçîáðàæåíà ëèíèÿ óðîâíÿ ïðè  1 <  2 .
TW2 = x2
 X2 ( )
 
©
  
 1 x1 =  2 x2
C
  2
             
E W1 = x1
O
 C
  1
 Ðèñ. 11.3
Åñëè  1 x1 >  2 x2 , òî ëèíèÿ óðîâíÿ îïðåäåëÿåòñÿ óðàâíåíèåì F2 ( , x) =
 2 x2 = C. Àíàëîãè÷íî ïðè  1 x1 <  2 x2 ñîîòâåòñòâóþùåå óðàâíåíèå èìååò
âèä F2 ( , x) =  1 x1 = C. Ýòî îçíà÷àåò, ÷òî ëèíèÿ óðîâíÿ ôóíêöèè F2 ( , x)
ïðåäñòàâëÿåò ñîáîé "óãîë". Ïðè  1 =  2 ìíîæåñòâî X2 ( ) ÿâëÿåòñÿ îòðåç-
êîì, ñîäåðæàùèì îïòèìàëüíóþ ïî Ïàðåòî ñòðàòåãèþ (1,1).
Èòàê, ñâåðòêà F1 ( , x) ïîçâîëÿåò ïîëó÷èòü ëèøü ÷àñòü îïòèìàëüíûõ
ïî Ïàðåòî ñòðàòåãèé, à ñâåðòêà F2 ( , x) ïîçâîëÿåò ïîñòðîèòü ìíîæåñòâî
S(X, W ). Îäíàêî, êîìáèíàöèÿ ýòèõ ñâåðòîê F2 ( , x) +  F1 ( , x) ïîçâîëÿåò
ñòðîèòü àïïðîêñèìàöèè ìíîæåñòâà P (X, W ).
Ðàññìîòðèì âîïðîñ î ïîñòðîåíèè ìíîæåñòâ P(X, W ) è S(X, W ). Âíà÷àëå
ðàññìîòðèì ñëó÷àé, êîãäà ìíîæåñòâî X êîíå÷íî, òî åñòü X = {x1 , ..., xn }.
Ðàññìîòðèì ñïîñîá ñðàâíåíèÿ ñòðàòåãèé x è x (â ñìûñëå Ïàðåòî):
Wi (x)   Wi (x ), i = 1, ..., s, W (x) = W(x ) (1)
5

Â ýòîì ñëó÷àå áóäåì ãîâîðèòü, ÷òî ñòðàòåãèÿ x ëó÷øå ñòðàòåãèè x ïî âåê-
òîðíîìó êðèòåðèþ W (x). Óñëîâèå (1) çàäàåò áèíàðíîå îòíîøåíèå íà ìíîæå-
ñòâå âñåõ ñòðàòåãèé X . Íåòðóäíî ïðîâåðèòü ÷òî ýòî îòíîøåíèå òðàíçèòèâíî.
Ðàññìîòðèì àëãîðèòì ïîñòðîåíèÿ ìíîæåñòâà P (X, W). Ïóñòü     ïåðå-
ìåííîå ìíîæåñòâî, ñîñòîÿùèå èç ïîïàðíî íåñðàâíèìûõ ñòðàòåãèé. Íàïîì-
íèì, ÷òî X = {x1 , ..., xn }.
Øàã 1. Ïîëîæèì   = {x1 }.
Ïóñòü ñäåëàíî k øàãîâ ïî àëãîðèòìó è ïîëó÷åíî ìíîæåñòâî  .
Øàã k + 1. Áåðåì î÷åðåäíóþ ñòðàòåãèþ xk +1 è ñðàâíèâàåì åå ñî âñåìè
ñòðàòåãèÿìè èç ìíîæåñòâà  . Çäåñü ìîãóò âñòðåòèòñÿ ñëåäóþùèå ñëó÷àè:
à) Íàéäåòñÿ ñòðàòåãèÿ èç ìíîæåñòâà  , êîòîðàÿ ëó÷øå ñòðàòåãèè xk+1 .
Â ýòîì ñëó÷àå ñòðàòåãèÿ xk+1 îòáðàñûâàåòñÿ, ìíîæåñòâî   íå ìåíÿåòñÿ è
ïåðåõîäèì ê ñëåäóþùåìó øàãó.
á) Ñòðàòåãèÿ xk+1 ëó÷øå íåêîòîðûõ ñòðàòåãèé èç ìíîæåñòâà  . Âñå
òàêèå õóäøèå ñòðàòåãèè îòáðàñûâàåì, ïîëó÷àåì ìíîæåñòâî P è ïîëàãàåì
  :=     {xk +1 }. Çàòåì ïåðåõîäèì ê ñëåäóþùåìó øàãó.
â) Ñòðàòåãèÿ xk +1 íå ñðàâíèìà ñî ñòðàòåãèÿìè èç ìíîæåñòâà  . Òîãäà
ïîëàãàåì   :=     {xk +1 } è ïåðåõîäèì ê ñëåäóþùåìó øàãó. Â ðåçóëüòàòå
ïîñëå n øàãîâ ïîëó÷àåì P(X, W ) =  .
Óïðàæíåíèå. Ïîêàæèòå, ÷òî ñëó÷àè à) è á) íå ìîãóò âûïîëíÿòüñÿ îäíî-
âðåìåííî.
Ýòîò àëãîðèòì ýôôåêòèâåí â òîì ñìûñëå, ÷òî íå ñâîäèòñÿ ê ïîëíîìó
ïåðåáîðó: åñëè êàêàÿ-òî ñòðàòåãèÿ îòáðîøåíà, òî îíà íå ó÷àñòâóåò â äàëü-
íåéøèõ ñðàâíåíèÿõ. Åñëè â (1) âñå íåðàâåíñòâà ñòðîãèå, òî àëãîðèòì ñòðîèò
ìíîæåñòâî S(X, W ).
Ïóñòü òåïåðü ìíîæåñòâî X ñîñòîèò èç áåñêîíå÷íîãî ÷èñëà ýëåìåíòîâ.
Îáû÷íî îíî çàäàåòñÿ â åâêëèäîâîì ïðîñòðàíñòâå îãðàíè÷åíèÿìè âèäà ðà-
âåíñòâ è íåðàâåíñòâ. Íà ìíîæåñòâå X ìîæíî çàäàòü ñåòêó èç êîíå÷íîãî
÷èñëà òî÷åê, à çàòåì ïðèìåíèòü ïðåäëîæåííûé àëãîðèòì.
Äðóãîé ïîäõîä ñîñòîèò â àíàëèòè÷åñêîì ìåòîäå ïîñòðîåíèÿ ìíîæåñòâà
P (X, W ), êîòîðîå ïûòàþòñÿ çàäàòü îãðàíè÷åíèÿìè âèäà ðàâåíñòâ èëè íåðà-
âåíñòâ. Òàêîé ïîäõîä îñíîâàí íà èñïîëüçîâàíèè óñëîâèé, êîòîðûì äîëæíû
óäîâëåòâîðÿòü îïòèìàëüíûå ïî Ïàðåòî èëè Ñëåéòåðó ñòðàòåãèè. Ïðèâåäåì
ïðèìåð òàêèõ óñëîâèé äëÿ ñëó÷àÿ âîãíóòûõ êðèòåðèåâ íà âûïóêëîì êîì-
ïàêòå åâêëèäîâà ïðîñòðàíñòâà Em .
Îïðåäåëåíèå. Ïóñòü x0   X. Ãîâîðÿò, ÷òî âåêòîð     Em çàäàåò â òî÷êå
x0 íàïðàâëåíèå, äîïóñòèìîå äëÿ ìíîæåñòâà X, åñëè íàéäåòñÿ òàêîå  0 > 0,
÷òî x0 +  x   X äëÿ âñåõ     [0,  0 ).
Ïî ñìûñëó, äâèãàÿñü èç òî÷êè x0 â íàïðàâëåíèè  , ìû íåêîòîðîå âðåìÿ
áóäåì îñòàâàòüñÿ â ìíîæåñòâå X. Ìíîæåñòâî âñåõ äîïóñòèìûõ â òî÷êå x0
íàïðàâëåíèé îáîçíà÷èì ÷åðåç L(x0 ).
Äëÿ x0 , âíóòðåííåé òî÷êè ìíîæåñòâà X, ëþáîå íàïðàâëåíèå ÿâëÿåòñÿ
äîïóñòèìûì. Äëÿ ãðàíè÷íîé òî÷êè êðóãà íà ïëîñêîñòè äîïóñòèìî ëþáîå
íàïðàâëåíèå, âåäóùåå âíóòðü êðóãà. Êàñàòåëüíîå íàïðàâëåíèå äîïóñòèìûì
íå ÿâëÿåòñÿ.
 6

Òåîðåìà 3.3. Ïóñòü âñå ÷àñòíûå êðèòåðèè Wi (x), i = 1, ..., s âîãíó-
òû è íåïðåðûâíî äèôôåðåíöèðóåìû íà âûïóêëîì êîìïàêòå X åâêëèäîâà
ïðîñòðàíñòâà Em . Òîãäà äëÿ òîãî, ÷òîáû x0 /
  S(X, W) íåîáõîäèìî è äîñòà-
òî÷íî, ÷òîáû íàøëîñü òàêîå äîïóñòèìîå íàïðàâëåíèå     L(x0 ), ÷òî
 (2)
(Wi (x0 ),  ) > 0, i = 1, ..., s.
  S(X, W ). Òîãäà
Äîêàçàòåëüñòâî. Íåîáõîäèìîñòü. Äîïóñòèì, ÷òî x0 /
  x   X : Wi (x) > Wi (x0 ), i = 1, ..., s. Ïî ñâîéñòâó âîãíóòûõ ôóíêöèé
(Wi (x0 ), x   x0 )   Wi (x)   Wi (x0 ) > 0, i = 1, ..., s,
òî åñòü óñëîâèå (2) âûïîëíåíî äëÿ äîïóñòèìîãî íàïðàâëåíèÿ   = x   x0 .
Äîñòàòî÷íîñòü. Ïðåäïîëîæèì,÷òî äëÿ íåêîòîðîãî     L(x0 ) âûïîëíåíî
óñëîâèå (2). Ïî îïðåäåëåíèþ äîïóñòèìîãî íàïðàâëåíèÿ íàéäåòñÿ òàêîå  0 >
0 , ÷òî äëÿ âñåõ
   : 0     <  0   x0 +      X.
Òîãäà ïî ôîðìóëå êîíå÷íûõ ïðèðàùåíèé Ëàãðàíæà
Wi (x0 +   )   Wi (x0 ) = (Wi (x0 +  i   ),   ) =  (Wi (x0 +  i   ),  ),
ãäå 0 <  i < 1. Ïóñòü   > +0. Òîãäà, èñïîëüçóÿ íåïðåðûâíîñòü ãðàäèåíòà
Wi (x), ïîëó÷èì
lim
 (Wi (x0 +  i   ),  ) = (Wi (x0 ),  ) > 0, i = 1, ..., s
  > +0
ïî óñëîâèþ (2). Îòñþäà ïðè ìàëîì   > 0
Wi (x0 +   )   Wi (x0 ) =  (Wi (x0 +   i  ),  ) > 0, i = 1, ..., s.
  S(X, W ).
Ïîýòîìó ñòðàòåãèÿ x0 +    ñòðîãî ëó÷øå, ÷åì ñòðàòåãèÿ x0 è x0 /
Îòìåòèì ñëåäóþùèé ÷àñòíûé ñëó÷àé. Äîïóñòèì, ÷òî êðèòåðèè Wi (x)
ñòðîãî âîãíóòû. Òîãäà S(X, W) = P(X, W ). Äåéñòâèòåëüíî, ïðåäïîëîæèì,
÷òî   x   S(X, W ) \ P (X, W ). Òîãäà   x : Wi (x)   Wi (x ), i = 1, ..., s, W (x) =
W (x ). Îòñþäà x = x è Wi ( x+x
2   Wi (x ), i = 1, ..., s. Ýòî
2 ) > W i (x )+Wi (x )
îçíà÷àåò, ÷òî x /
  S(X, W ) (ïðîòèâîðå÷èå). Ïîýòîìó äëÿ ñòðîãî âîãíóòûõ
êðèòåðèåâ òåîðåìà 3.3 äàåò íåîáõîäèìûå è äîñòàòî÷íûå óñëîâèÿ äëÿ îïòè-
ìàëüíûõ ïî Ïàðåòî ñòðàòåãèé. Ðàññìîòðèì ïðèìåð èñïîëüçîâàíèÿ ïîëó÷åí-
íûõ óñëîâèé.
Ïðèìåð. Ïóñòü x = (x1 , ..., xm), K = {1, ..., m}. Äëÿ êàæäîãî ïîäìíîæå-
ñòâà J   K ðàññìîòðèì êðèòåðèé:
 m
WJ (x) = 1  
 xk +
 xk .
 x2
k  
k =1
 k  J
 k /
 J
7

Âñåãî 2m êðèòåðèåâ. Ïóñòü
 m
X = {x   Em|
 x2
k   1}.
k=1
Íàéäåì P (X, W ). Îòìåòèì, ÷òî êàæäûé ÷àñòíûé êðèòåðèé WJ (x) ñòðî-
ãî âîãíóò (äîêàæèòå) è P (X, W ) = S(X, W). Óñëîâèå (2) çàâèñèò îò  
ñ òî÷íîñòüþ äî ïîëîæèòåëüíîãî ìíîæèòåëÿ. Ïîýòîìó íà âåêòîð   ìîæ-
íî íàëîæèòü óñëîâèå íîðìèðîâêè: m
 | k | = 1. Âîçüìåì ñíà÷àëà x0  
k =1
âíóòðåííþþ òî÷êó ìíîæåñòâà X, òî åñòü m
 (x0
k )2 < 1. Â ýòîì ñëó÷àå
k =1
 | k | = 1}. Íàéäåì ãðàäèåíò êàæäîãî ÷àñòíîãî êðè-
L(x0 ) = {    Em | m
k =1
òåðèÿ
 WJ (x)
 ± 1,
 =  xk
xk
1   m
 x2
k
k=1
ãäå +1, åñëè k /
  J è  1, åñëè k   J. Îòñþäà óñëîâèå (2) çàïèøåòñÿ â âèäå
  
( , WJ (x0 )) =  (x0 ,  )
  k +
  k > 0 (2)
 k J
 k /
 J
1   m
 (x0
k )2
k=1
äëÿ âñåõ J   K. Ïîêàæåì, ÷òî ýòà ñèñòåìà íåðàâåíñòâ ýêâèâàëåíòíà îäíîìó
íåðàâåíñòâó. Äåéñòâèòåëüíî, âîçüìåì J = {k |  k   0}. Òîãäà   m
  k +
k  J
m
 | k | =  1   íàèìåíüøåå çíà÷åíèå ñóììû. Îòñþäà èç (2)
  k =   m
k  J
k /
  J
 (x0 ,  )
   1 > 0.
1   m
 (x0
k )2
k =1
 
Ýòî îäíî èç íåðàâåíñòâ â (2). Íî âñå îñòàëüíûå ñëåäóþò èç íåãî. Èòàê, x0 /
[ (x0 ,  )] >
S(X, W )        L(x0 ) :  (x0 ,  ) > 1   m
 (x0
k )2   max
   L( x0 )
k= 1
1   m
 (x0
k )2 .
k=1
Íàéäåì ìàêñèìóì, ñòîÿùèé â ëåâîé ÷àñòè ïîñëåäíåãî íåðàâåíñòâà. Èìå-
åì
 m
  (x0 ,  )   max
 | k | = max
 |x0
 |x0
l |,
j |
j | = |x0
1  j  m
1  j  m
k =1
8

ãäå ðàâåíñòâî äîñòèãàåòñÿ ïðè   = (0, ..., +1
 , ...0). Ïîëó÷èëè max
[ (x0 ,  )] =
   L(x 0 )
l
max
 |x0
j |. Èòàê,
1  j  m
 m
  S(X, W)   max
x0 /
 |x0
 (x0
j | > 1  
k )2 .
1  j  m
k =1
Îòñþäà
 m
 x0   S(X, W)   max
 |x0
 (x0
j |   1  
k )2 .
1  j  m
k =1
Ýòî íåðàâåíñòâî è çàäàåò ìíîæåñòâî S(X, W ) = P (X, W ) âíóòðè X.
Åñëè x0 ïðèíàäëåæèò ãðàíèöå ìíîæåñòâà X, òî åñòü m
 (x0
k)2 = 1, òî
k=1
òî÷êà íå áóäåò îïòèìàëüíîé ïî Ïàðåòî, òàê êàê ìàëîå ñìåùåíèå îò x0 âäîëü
 (xk )2 .
ðàäèóñà ïðèâåäåò ê ðåçêîìó âîçðàñòàíèþ êîðíÿ 1   m
k=1
Ïóñòü m = 2. Òîãäà P(X, W ) çàäàåòñÿ äâóìÿ íåðàâåíñòâàìè
(x0
1 )2   1   (x0
1 )2   (x0
2 )2 , (x0
2 )2   1   (x0
1 )2   (x0
2 )2
è ïðåäñòàâëÿåò ñîáîé ïåðåñå÷åíèå äâóõ ýëëèïñîâ.
Ðàññìîòðèì òåïåðü îáùóþ çàäà÷ó ïðèíÿòèÿ ðåøåíèé. Ïóñòü X   ìíî-
æåñòâî ñòðàòåãèé.
Îïðåäåëåíèå. Áèíàðíûì îòíîøåíèåì R íà ìíîæåñòâå X íàçûâàåòñÿ ïîä-
ìíîæåñòâî R   X   X.
Áèíàðíîå îòíîøåíèå R çäåñü èíòåðïðåòèðóåòñÿ ñëåäóþùèì îáðàçîì: åñ-
ëè (x, x )   R, òî äëÿ ËÏÐ ñòðàòåãèÿ x ëó÷øå ñòðàòåãèè x (èëè íå õóæå,
÷åì x ). Âìåñòî (x, x )   R îáû÷íî èñïîëüçóþò áîëåå ïðîñòóþ çàïèñü xRx .
Åñëè (x, x ) /
  R, òî áóäåì ïèñàòü xRx .
Áèíàðíîå îòíîøåíèå íàçûâàåòñÿ:
à) ðåôëåêñèâíûì, åñëè xRx  x   X;
á) àíòèðåôëåêñèâíûì, åñëè xRx  x   X;
â) ñèììåòðè÷íûì, åñëè xRy   yRx  x, y   X;
ã) àñèììåòðè÷íûì, åñëè xRy   yRx  x, y   X;
ä) òðàíçèòèâíûì, åñëè xRy, yRz   xRz  x, y , z   X;
ã) àöèêëè÷íûì, åñëè  x1 , ..., xk   X : x1 Rx2 R...RxkRx1 .
Ðàññìîòðèì ïðèìåðû. R   áèíàðíîå îòíîøåíèå ñðàâíåíèÿ ñòðàòåãèé
ïî âåêòîðíîìó êðèòåðèþ â íåñòðîãîì ñìûñëå (ïî Ïàðåòî) èëè â ñòðîãîì
ñìûñëå (ïî Ñëåéòåðó). Ýòî òðàíçèòèâíûå, àñèììåòðè÷íûå îòíîøåíèÿ.
Óïðàæíåíèå. Äîêàæèòå, ÷òî àíòèðåôëåêñèâíîå òðàíçèòèâíîå áèíàðíîå
îòíîøåíèå àöèêëè÷íî.
 9

Îïðåäåëåíèå. Ìíîæåñòâî
C(X, R) = {x   X | xRx   x Rx} (1)
íàçûâàåòñÿ ÿäðîì áèíàðíîãî îòíîøåíèÿ R.
Ïî ñìûñëó åñëè x   C(X, R) è x íå õóæå, ÷åì x , òî è x íå õóæå, ÷åì x.
Åñëè áèíàðíîå îòíîøåíèå R àñèììåòðè÷íî, òî ÿäðó ìîæíî äàòü ýêâè-
âàëåíòíîå, áîëåå óäîáíîå îïðåäåëåíèå:
C(X, R) = {x   X |   x   X : xRx }. (2)
Äîêàæåì, ÷òî â ýòîì ñëó÷àå ìíîæåñòâà (1) è (2) ñîâïàäàþò. Ïóñòü x   (1).
Äîêàæåì, ÷òî x   (2). Äåéñòâèòåëüíî, åñëè   x   X : xRx , òî ïî ñâîéñòâó
àñèììåòðè÷íîñòè x Rx, ÷òî ïðîòèâîðå÷èò îïðåäåëåíèþ (1). Îáðàòíî, ïóñòü
x   (2), äîêàæåì, ÷òî x   (1). Íî ýòî î÷åâèäíî, ïîñêîëüêó   x   X : xRx
è íåò ïîñûëêè äëÿ èìïëèêàöèè èç (1).
Äëÿ îòíîøåíèé ñðàâíåíèÿ ïî Ïàðåòî è Ñëåéòåðó ñîîòâåòñòâóþùèìè ÿä-
ðàìè ÿâëÿþòñÿ ìíîæåñòâà P (X, W ) è S(X, W ).
Óïðàæíåíèå. Ïóñòü X   êîíå÷íîå ìíîæåñòâî, à áèíàðíîå îòíîøåíèå R
àöèêëè÷íî. Äîêàæèòå, ÷òî ÿäðî C(X, R) íå ïóñòî.
Ïðèìåð. Ïóñòü X = {x1 , x2 , x3 }, à áèíàðíîå îòíîøåíèå çàäàíî îðèåíòè-
ðîâàííûì ãðàôîì:
B
x2
r

x1
r
r
r
r
r
 c
T
r
r
x3
 Ðèñ. 11.4
Çäåñü îòíîøåíèå R íå ÿâëÿåòñÿ àñèììåòðè÷íûì, òàê êàê x2 Rx3 Rx2 . Ïî-
ýòîìó èñïîëüçóåì ïåðâîå îïðåäåëåíèå ÿäðà: C(X, R) = {x3 }. Åñëè áû ìû
èñïîëüçîâàëè âòîðîå îïðåäåëåíèå, òî ÿäðî îêàçàëîñü áû ïóñòûì.
Â êà÷åñòâå ïðèëîæåíèÿ îáùåé çàäà÷è ïðèíÿòèÿ ðåøåíèé ïîñòàâèì çàäà-
÷ó ñîêðàùåíèÿ ìíîæåñòâà îïòèìàëüíûõ ïî Ïàðåòî ñòðàòåãèé P (X, W ) íà
îñíîâå ýêñïåðòíîé èíôîðìàöèè. Ïîäõîä áûë ïðåäëîæåí Â.Â.Ïîäèíîâñêèì.
Íà÷íåì ñ ïðèìåðà. Ó÷åíèêè x1 è x2 èìåþò ñëåäóþùèå îöåíêè ïî äâóì
 ì ë
ïðåäìåòàì (êðèòåðèÿì), ìàòåìàòèêå è ëèòåðàòóðå:
 . Ó÷åíèêè
x1 3 5
x2 5 4
íå ñðàâíèìû ïî âåêòîðíîìó êðèòåðèþ. Îäíàêî, ñðàâíåíèå âîçìîæíî, åñëè
åñòü ýêñïåðòíàÿ èíôîðìàöèÿ î ñðàâíèòåëüíîé âàæíîñòè èëè ðàâíîöåííî-
ñòè êðèòåðèåâ. Åñëè ïðåäìåòû ðàâíîöåííû, òî ó÷åíèê x2 ó÷èòñÿ îäèíàêîâî
ñ ãèïîòåòè÷åñêèì ó÷åíèêîì x3 | 4 | 5 |, êîòîðûé ó÷èòñÿ ëó÷øå ó÷åíèêà x1 .
10

Ïîýòîìó ó÷åíèê x2 ó÷èòñÿ ëó÷øå, ÷åì x1 . Ïóñòü ìàòåìàòèêà âàæíåå ëèòå-
ðàòóðû. Òîãäà x2 ó÷èòñÿ ëó÷øå x3 , òàê êàê ïî áîëåå âàæíîìó ïðåäìåòó ó x2
ïÿòåðêà. Ñëåäîâàòåëüíî, ïî òðàíçèòèâíîñòè x2 ó÷èòñÿ ëó÷øå, ÷åì x1 . Åñëè
ëèòåðàòóðà âàæíåå ìàòåìàòèêè, òî ó÷åíèê x3 ó÷èòñÿ ëó÷øå x2 , íî x1 è x2
íå ñðàâíèìû, ïîñêîëüêó x1 èìååò ïÿòåðêó ïî áîëåå âàæíîìó ïðåäìåòó.
Òåïåðü ïðîâåäåì íåîáõîäèìóþ ôîðìàëèçàöèþ. Áóäåì ãîâîðèòü, ÷òî ÷àñò-
íûå êðèòåðèè Wi (x) è Wj (x) îäíîðîäíû, åñëè max
 Wi (x) = max
 Wj (x) è
x  X
x  X
min
 Wi (x) = min
 Wj (x), òî åñòü êðèòåðèè Wi (x) è Wj (x) èìåþò îäèíàêîâûå
x  X
x  X
äèàïàçîíû èçìåíåíèÿ.
Åñëè êðèòåðèè Wi (x) è Wj (x) íå ÿâëÿþòñÿ îäíîðîäíûìè è íå ÿâëÿþòñÿ
êîíñòàíòàìè, òî èõ ìîæíî ñäåëàòü îäíîðîäíûìè, çàìåíèâ êðèòåðèé Wj (x)
íà êðèòåðèé  Wj (x) +  , ãäå   > 0 è   ñîîòâåòñòâóþùèì îáðàçîì ïîäîáðàí-
íûå êîíñòàíòû.
Óïðàæíåíèå. Íàéäèòå ÿâíûå âûðàæåíèÿ äëÿ êîíñòàíò   è  .
Â äàëüíåéøåì áóäåì ñ÷èòàòü, ÷òî â âåêòîðíîì êðèòåðèè W (x) âñå ÷àñò-
íûå êðèòåðèè ïîïàðíî îäíîðîäíû.
Ïóñòü I = {1, ..., s}   ìíîæåñòâî íîìåðîâ êðèòåðèåâ. Èíôîðìàöèÿ îò
ËÏÐ î ñðàâíèòåëüíîé âàæíîñòè èëè ðàâíîöåííîñòè êðèòåðèåâ çàäàíà ìíî-
æåñòâàìè A1 , A2   I   I. Çäåñü A1   ìíîæåñòâî ïàð (r, t) íîìåðîâ ðàâíîöåí-
íûõ êðèòåðèåâ, A2   ìíîæåñòâî òàêèõ ïàð (r, t), ÷òî êðèòåðèé Wr (x) âàæíåå
êðèòåðèÿ Wt (x). A1 è A2 ìîæíî ðàññìàòðèâàòü êàê áèíàðíûå îòíîøåíèÿ íà
I : A1   îòíîøåíèå ðàâíîöåííîñòè êðèòåðèåâ, à A2   îòíîøåíèå èõ ñòðîãîãî
ïðåäïî÷òåíèÿ. Åñòåñòâåííî ïðåäïîëîæèòü, ÷òî îòíîøåíèå A1 ñèììåòðè÷íî
è òðàíçèòèâíî, îòíîøåíèå A2 àñèììåòðè÷íî è òðàíçèòèâíî. Èíôîðìàöèÿ,
âûðàæåííàÿ â áèíàðíûõ îòíîøåíèÿõ A1 è A2 , äîëæíà áûòü íåïðîòèâîðå-
÷èâîé â òîì ñìûñëå, ÷òî íåëüçÿ ïîñòðîèòü öåïî÷êó âèäà rB1 tB2 ...Bk r, ãäå
Bi = A1 èëè A2 è íå äëÿ âñåõ i Bi = A1 . Íàïðèìåð, åñëè èíôîðìàöèÿ
íåïðîòèâîðå÷èâà, òî íåëüçÿ ïîñòðîèòü öåïî÷êó âèäà 1A1 2A2 3A1 1.
Íåïðîòèâîðå÷èâîñòü ýêñïåðòíîé èíôîðìàöèè ìîæíî çàäàòü ñëåäóþùèì
ñïîñîáîì. Îïðåäåëèì íà ìíîæåñòâå I áèíàðíîå îòíîøåíèå: r t âûïîëíåíî
òîëüêî â òîì ñëó÷àå, êîãäà ñóùåñòâóåò öåïî÷êà i0 B1 i1 B2 ....Bk ik , ãäå i0 =
r, ik = t, à êàæäîå áèíàðíîå îòíîøåíèå Bl , l = 1, ..., k, ðàâíî ëèáî A1 ,
ëèáî A2 è ñðåäè íèõ åñòü ïî êðàéíåé îäíî îòíîøåíèå A2 . Íåòðóäíî âèäåòü,
÷òî áèíàðíîå îòíîøåíèå   òðàíçèòèâíî. Íåïðîòèâîðå÷èâîñòü èíôîðìàöèè
ñîñòîèò â òîì, ÷òî áèíàðíîå îòíîøåíèå   àíòèðåôëåêñèâíî.
Â åâêëèäîâîì ïðîñòðàíñòâå Es âåêòîðíûõ îöåíîê y = W(x) îïðåäåëèì
ñëåäóþùèå áèíàðíûå îòíîøåíèÿ.
Îòíîøåíèå Ïàðåòî  
P = {(y , y )   Es   Es | yi   yi , i = 1, ..., s, y = y }.
Äëÿ ïàðû (r, t), r = t è âåêòîðà y ââåäåì âåêòîð yr t, ïîëó÷åííûé èç y ïåðå-
ñòàíîâêîé r-é è t-é êîìïîíåíò.
Ïóñòü rA1 t. Îïðåäåëèì áèíàðíîå îòíîøåíèå Sr t íà Es : y Sr tz   z = yr t .
Åñëè êðèòåðèè Wr è Wt ðàâíîöåííû äëÿ ËÏÐ, òî è âåêòîðíûå îöåíêè y è
z ðàâíîöåííû äëÿ íåãî ïðè ySr t z.
 11

Ïóñòü rA2 t. Îïðåäåëèì áèíàðíîå îòíîøåíèå Tr t : yTr t z   z = y r t, yr >
yt. Ïî ñìûñëó åñëè r-é êðèòåðèé ïðåäïî÷òèòåëüíåé t-ãî, òî îöåíêà y ïðåä-
ïî÷òèòåëüíåé äëÿ ËÏÐ îöåíêè z , ïîñêîëüêó ïî áîëåå ïðåäïî÷òèòåëüíîìó
êðèòåðèþ çíà÷åíèå áîëüøå â îöåíêå y.
Îïðåäåëèì, íàêîíåö, ðåçóëüòèðóþùåå áèíàðíîå îòíîøåíèå R : y Ry , åñ-
ëè ñóùåñòâóåò òàêàÿ ïîñëåäîâàòåëüíîñòü z0 , z1 , ..., zk , ÷òî y = z0 , y = zk
è z0 H0 z1 H1 . . . Hk  1 zk , ãäå áèíàðíûå îòíîøåíèÿ Hi   {P, Sr t : rA1 t, Tr t :
rA2 t} è ïðè ýòîì íå âñå Hl = Sr t. Â ýòîì ñëó÷àå áóäåì ãîâîðèòü, ÷òî ïîñëå-
äîâàòåëüíîñòü z0 , z1 , ..., zk ñâÿçûâàåò âåêòîðíûå îöåíêè y è y
Ëåììà 1. Áèíàðíîå îòíîøåíèå R   òðàíçèòèâíîe è àöèêëè÷íîå.
Äîêàçàòåëüñòâî. Òðàíçèòèâíîñòü îòíîøåíèÿ R î÷åâèäíà: åñëè yRy è
y Ry , òî ïîñëåäîâàòåëüíîñòè âåêòîðíûõ îöåíîê, ñâÿçûâàþùèå áèíàðíûìè
îòíîøåíèÿìè y ñ y è y ñ y ñëåäóåò îáúåäèíèòü. Îòñþäà ñëåäóåò, ÷òî y Ry .
Äîêàæåì àöèêëè÷íîñòü îòíîøåíèÿ R. Ïðåäïîëîæèì, ÷òî ñóùåñòâóåò
òàêàÿ ïîñëåäîâàòåëüíîñòü âåêòîðíûõ îöåíîê y1 , ..., yk , ÷òî yRy 1 R...Ryk Ry .
Èç òðàíçèòèâíîñòè îòíîøåíèÿ R âûòåêàåò, ÷òî y Ry. Ïîýòîìó ñóùåñòâóåò
ñëåäóþùàÿ öåïî÷êà ñâÿçàííûõ áèíàðíûìè îòíîøåíèÿìè âåêòîðíûõ îöå-
íîê: yH1 z1 H1 . . . Hk  1 zk  1 Hk y. Åñëè ñðåäè îòíîøåíèé Hl âñòðå÷àåòñÿ îò-
íîøåíèå P, òî ïîëó÷èì ïðîòèâîðå÷èå, òàê êàê ñóììà êîìïîíåíò âåêòîðîâ
âäîëü öåïî÷êè ëèáî íå ìåíÿåòñÿ (ïðè Hl = Sr t èëè Hl = Tr t ), ëèáî óáû-
âàåò ( ïðè Hl = P ). Ïóñòü îòíîøåíèå P â öåïî÷êå íå âñòðå÷àåòñÿ. Òîãäà
âäîëü öåïî÷êè âåêòîðû ïîëó÷àþòñÿ ïåðåñòàíîâêîé êîìïîíåíò è îáÿçàòåëü-
íî âñòðåòèòñÿ îòíîøåíèå Tr t . Áåç ïîòåðè îáùíîñòè ìîæíî ñ÷èòàòü, ÷òî
H1 = Tr t. Äàëåå, Hl = Til j l èëè Hl = Si lj l ïðè l = 2, ..., k. Òîãäà yr > yt
è rA2 t, i2 A1 (A2 )j2 , ..., ik A1 (A2 )jk .
Ââåäåì ìíîæåñòâî I+ = {i   I | i t}. Ïî ñìûñëó â ìíîæåñòâî I+ âõîäÿò
íîìåðà êðèòåðèåâ, áîëåå âàæíûõ, ÷åì t-é êðèòåðèé. Íåòðóäíî âèäåòü, ÷òî
r   I+ , t /
  I+ . Äåéñòâèòåëüíî, èç rA2 t ñëåäóåò, ÷òî r t, à t t âûòåêàåò èç
àíòèðåôëåêñèâíîñòè áèíàðíîãî îòíîøåíèÿ  .
Âîçüìåì ëþáóþ ïàðó (il , jl ), l = 2, ..., k. Åñëè jl   I+ , òî il   I+, ïîñêîëü-
êó èç il A1 (A2 )jl  t ñëåäóåò, ÷òî il  t. Ïîýòîìó äëÿ ïàðû (il , jl ) âîçìîæíû
òîëüêî ñëåäóþùèå ñëó÷àè:
1) il , jl   I+;
2) il , jl /
  I+;
3) il   I+ , jl /
  I+ .
Â ïåðâûõ äâóõ ñëó÷àÿõ
 zl
i , ïîñêîëüêó âåêòîð zl ïîëó÷åí
 zl  1
i =
 i  I +
 i  I +
èç âåêòîðà zl  1 ïåðåñòàíîâêîé il -é è jl -é êîìïîíåíò.
Ïîêàæåì, ÷òî â òðåòüåì ñëó÷àå íåîáõîäèìî âûïîëíåíî il A2 jl . Äåéñòâè-
òåëüíî, åñëè il A1 jl , òî èç ñèììåòðè÷íîñòè îòíîøåíèÿ A1 ñëåäóåò, ÷òî jl A1 il  t  
jl  t   jl   I+ , ÷òî ïðîòèâîðå÷èò âûáîðó jl /
  I+ . Íî il A2 jl îçíà÷àåò, ÷òî
zl  1 Ti l jl zl . Îòñþäà ïîëó÷àåì íåðàâåíñòâî
 zl
 zl  1
i >
i .
i   I+
 i  I +
12

Ñëåäîâàòåëüíî,
 yi >
 z1
 z 2
 yi
i   ...  
i  
 i  I +
 i  I+
 i   I+
 i  I +
(ïðîòèâîðå÷èå).
Ïóñòü P (X, W ) = {x1 , ..., xm } è P (Y ) = {yi = W (xi ), i = 1, ..., m}  
ñîîòâåòñòâóþùèå âåêòîðíûå îöåíêè. Çàäà÷ó ñóæåíèÿ ìíîæåñòâà P (X, W )
ìîæíî ñôîðìóëèðîâàòü òàê: òðåáóåòñÿ íàéòè ÿäðî C(P (Y ), R) áèíàðíîãî
îòíîøåíèÿ R íà ìíîæåñòâå P(Y ). Ïîñêîëüêó îòíîøåíèå R àöèêëè÷íî è
òðàíçèòèâíî, à ìíîæåñòâî P (Y ) êîíå÷íî, òî ÿäðî C(P (Y ), R) íå ïóñòî.
Îñíîâíàÿ çàäà÷à çäåñü ñîñòîèò â ñëåäóþùåì. Äëÿ äâóõ âåêòîðíûõ îöå-
íîê y è y òðåáóåòñÿ âûÿñíèòü, ñâÿçàíû ëè îíè îòíîøåíèåì R. Â ÷àñòíûõ
ñëó÷àÿõ ýòà çàäà÷à ðåøàåòñÿ íåñëîæíî. Ðàññìîòðèì ïðèìåðû.
1. Ïóñòü âñå ÷àñòíûå êðèòåðèè ðàâíîöåííû, ò.å. A1 = I   I, à A2 =  .
×òîáû ñðàâíèòü âåêòîðíûå îöåíêè y è y , íóæíî ñíà÷àëà óïîðÿäî÷èòü èõ
êîìïîíåíòû, à ïîòîì ñðàâíèòü èõ ïî Ïàðåòî. Áîëåå ôîðìàëüíî, îïðåäåëèì
âåêòîð  (y )   Es , îáðàçîâàííûé èç êîìïîíåíò âåêòîðà y , ðàñïîëîæåííûõ â
ïîðÿäêå óáûâàíèÿ:
  1 (y)    2 (y)   ...    s (y ),
ãäå  1 (y ) = min
 yi   íàèáîëüøàÿ êîìïîíåíòà âåêòîðà y, à  s (y) = max
 yi  
1  i  s
1   i  s
íàèìåíüøàÿ.
Ëåììà 2. Åñëè yP y , òî  (y)P  (y ).
Äîêàçàòåëüñòâî. Çàìåòèì, ÷òî  1 (y)    1 (y ). Ïðåäïîëîæèì, ÷òî íàé-
äåòñÿ íîìåð k   {1, ..., s   1}, äëÿ êîòîðîãî âûïîëíåíû íåðàâåíñòâà
 i (y)    i (y ), i = 1, ..., k,  k+ 1 (y) <  k+1 (y ).
Íî s   k êîìïîíåíòàì  k+1 (y ), ...,  s (y) âåêòîðà y äîëæíû ñîîòâåòñòâîâàòü
ñòîëüêî æå êîìïîíåíò âåêòîðà y , íå ïðåâîñõîäÿùèõ  k +1 (y), ÷òî ïðîòèâî-
ðå÷èò âûáîðó k. Èòàê,  i (y )    i (y ), i = 1, ..., s, è õîòÿ áû îäíî èç ýòèõ
íåðàâåíñòâ   ñòðîãîå.
Óòâåðæäåíèå. Åñëè A1 = I   I, òî yRy âûïîëíåíî òîãäà è òîëüêî òîãäà,
êîãäà  (y)P  (y ).
Äîêàçàòåëüñòâî. Ïóñòü yRy . Òîãäà ñóùåñòâóåò òàêàÿ ïîñëåäîâàòåëü-
íîñòü âåêòîðíûõ îöåíîê z0 , z1 , ..., zk , ÷òî y = z0 , y = zk è z0 H0 z1 H1 . . . Hk  1 z k,
ãäå áèíàðíûå îòíîøåíèÿ Hi   {P, Sr t : rA1 t} è ïðè ýòîì íàéäåòñÿ òàêîå
s, ïðè êîòîðîì Hs = P. Èç ëåììû 2 ñëåäóåò, ÷òî  (zs  1 )P  (zs ). Äëÿ l = s
ëèáî  (zl  1 )P  (zl ), ëèáî  (zl  1 ) =  (zl ). Îòñþäà  (y )P (y ).
Ïóñòü  (y)P  (y ). Òîãäà íàéäåòñÿ ïîñëåäîâàòåëüíîñòü âèäà
yH1 z1 H2 ...Hs  1  (y)P  (y )Hs +1 zs +1 ...Hk y ,
ãäå Hl   {Sr t | rA1 t}, l = s. Îòñþäà y Ry .
13

Ðàññìîòðèì êîíêðåòíûé ïðèìåð. Ïóñòü s = 3, à P (X, W ) = {x1 , x2 , ..., x5 }.
Ñîîòâåòñòâóþùèå âåêòîðíûå îöåíêè óêàçàíû â òàáëèöå
y 1 3 5 3
y 2 4 4 3
y 3 5 3 2
y 4 2 3 5
y 5 4 2 4
Çäåñü y1 Ry3 , y1 Ry4 , y2 Ry5 ,  (y 1 ) è  (y 2 ) íå ñðàâíèìû ïî P. Ïîýòîìó
C((Y ), R) = {y 1 , y2 } è îñòàþòñÿ äâå îïòèìàëüíûå ïî Ïàðåòî ñòðàòåãèè x1 è
x2 .
 2. Ïóñòü (X, W) = {x1 , x2 , x3 , x4 } - ó÷åíèêè ñ îöåíêàìè ïî ÷åòûðåì ïðåä-
ìåòàì, A1 = {(1, 3)}, A2 = {(2, 4), (2, 3)}.
y1 5 5 4 4
y2 5 4 5 4
y3 5 4 4 5
y4 4 4 5 5
Çäåñü y 1 T2 4 y 3 , y1 T2 3 y2 , y1 T2 4 y3 S1 3 y4   C(P(Y ), R) = {y1 } è îñòàåòñÿ
åäèíñòâåííûé íàèëó÷øèé ó÷åíèê x1 .
Ðàññìîòðèì ïðèìåð èñïîëüçîâàíèÿ áèíàðíûõ îòíîøåíèé â çàäà÷å ïðî-
åêòèðîâàíèÿ óïðàâëÿåìûõ äèíàìè÷åñêèõ îáúåêòîâ.
Äèíàìè÷åñêèé îáúåêò çàäàåòñÿ ñèñòåìîé îáûêíîâåííûõ äèôôåðåíöè-
àëüíûõ óðàâíåíèé
  
 (1)
z = f (z, u, x), z(t0 ) = z0 ,
ãäå z   Z(x) = {z   Em | gj (z)   wj (x), j = 1, ..., l}   âåêòîð ôàçîâûõ
ïåðåìåííûõ, x   X   âåêòîð êîíñòðóêòèâíûõ ïàðàìåòðîâ (ñòðàòåãèÿ ËÏÐ)
è u   U   óïðàâëåíèå.
Ê òàêîìó êëàññó îáúåêòîâ îòíîñÿòñÿ ëåòàòåëüíûé àïïàðàò, ðîáîò-ìàíèïóëÿòîð,
ýëåêòðè÷åñêàÿ öåïü è ò.ï. Âîçíèêàåò âîïðîñ, êàê ñðàâíèòü äâà âàðèàíòà x è
x êîíñòðóêöèé äèíàìè÷åñêîé ñèñòåìû?
Ïóñòü H   ìíîæåñòâî â Em . Îáîçíà÷èì ÷åðåç convH âûïóêëóþ îáî-
ëî÷êó ìíîæåñòâà H, ò. å. ïåðåñå÷åíèå âñåõ âûïóêëûõ ìíîæåñòâ èç Em ,
ñîäåðæàùèõ ìíîæåñòâî H. Âûïóêëàÿ îáîëî÷êà convH ïðåäñòàâëÿåò ñîáîé
  j zj , ãäå
ñîâîêóïíîñòü âñåâîçìîæíûõ âûïóêëûõ êîìáèíàöèé âèäà k
j =1
k
  j = 1,  j   0, zj   H, j = 1, ..., k.
j=1
Ñïðàâåäëèâî ñëåäóþùåå óòâåðæäåíèå: âûïóêëàÿ îáîëî÷êà êîìïàêòà â Em
ÿâëÿåòñÿ âûïóêëûì êîìïàêòîì.
Ðàññìîòðèì ìíîæåñòâî
= conv{f   Em | f = f (z, u, x), u   U}
G(x, z) = convf (z, U, x) de f
14

  âûïóêëóþ îáîëî÷êó âåêòîðîãðàììû f (z, U, x) ïðàâîé ÷àñòè ñèñòåìû (1).
Â äàëüíåéøåì ïðåäïîëàãàåòñÿ, ÷òî ôóíêöèÿ f (z, u, x) íåïðåðûâíà, à U  
êîìïàêò åâêëèäîâà ïðîñòðàíñòâà. Òîãäà âåêòîðîãðàììà f (z, U, x)   êîì-
ïàêò, à G(x, z)   âûïóêëûé êîìïàêò â Em .
Îïðåäåëèì áèíàðíîå îòíîøåíèå
xRx   G(x, z)   G(x , z),   z   Z(x )   Z(x ). (2)
Èíòóèòèâíî ÿñíî, ÷òî îáúåêò x îáëàäàåò á 
îëüøèìè äèíàìè÷åñêèìè âîç-
ìîæíîñòÿìè, ÷åì îáúåêò x . Ýòî îçíà÷àåò, ÷òî óïðàâëÿÿ îáúåêòîì x, ìîæ-
íî ïîëó÷èòü áîëåå øèðîêîå ìíîæåñòâî òðàåêòîðèé, ÷åì óïðàâëÿÿ îáúåêòîì
x .1
 Íåòðóäíî âèäåòü, ÷òî áèíàðíîå îòíîøåíèå R òðàíçèòèâíî è ìîæíî ðå-
øàòü çàäà÷ó ïîèñêà ÿäðà C(X, R).
Çàïèøåì áèíàðíîå îòíîøåíèå R â ýêâèâàëåíòíîì âèäå. Ïóñòü S = {s  
Em | |s| = 1}   åäèíè÷íàÿ ñôåðà â Em . Îïðåäåëèì íà S îïîðíóþ ôóíêöèþ
ìíîæåñòâà G(x, z):
  (s, x, z) = max
(f, s).
f  G (x, z )
Îòìåòèì õàðàêòåðíîå ñâîéñòâî îïîðíûõ ôóíêöèé:
G(x, z)   G(x , z )    (s, x, z)    (s, x , z)   s   S.
Èìïëèêàöèÿ   î÷åâèäíà. Èìïëèêàöèÿ   äîêàçûâàåòñÿ ñ ïîìîùüþ òåîðåìû
îá îòäåëÿþùåé ãèïåðïëîñêîñòè.
Ñäåëàåì ñëåäóþùåå ïðåäïîëîæåíèå:
Z (x )   Z (x)   wj (x)   wj (x ), j = 1, ..., l.
Òîãäà (2) ìîæíî çàïèñàòü â âèäå
 (s, x, z)    (s, x , z),   s   S,  z   Z(x ),
wj (x )   wj (x), j = 1, ..., l.
 (3)
Ïåðâàÿ ãðóïïà íåðàâåíñòâ ýêâèâàëåíòíà âêëþ÷åíèþ G(x, z)   G(x , z), à
âòîðàÿ   âêëþ÷åíèþ Z(x )   Z (x). Çàìåòèì, ÷òî ïåðâóþ ãðóïïó íåðàâåíñòâ
ìîæíî çàïèñàòü â âèäå
 (x, x , z) = min
 ( (s, x, z)    (s, x , z ))   0   z   Z(x ).
s   S
Ïðèìåð. Ðàññìîòðèì ñèñòåìó
 
z1 = z2 ,  
z 2 = P u   kz 2 , z1 , z2   E3 , u   U = {u   E3 | |u|   1}.
Ýòî óðàâíåíèÿ äâèæåíèÿ òî÷å÷íîãî îáúåêòà, z1   ïðîñòðàíñòâåííûå êîîð-
äèíàòû, z2   ñêîðîñòü. Âòîðàÿ ãðóïïà óðàâíåíèé   óðàâíåíèÿ ñèë. Çäåñü
1 Ýòîò ôàêò ñòðîãî ôîðìóëèðóåòñÿ è îáîñíîâûâàåòñÿ â êíèãå Í.Í.Êðàñîâñêîãî è
À.È.Ñóááîòèíà "Ïîçèöèîííûå äèôôåðåíöèàëüíûå èãðû".   Ì.: Íàóêà, 1974.
15

P   òÿãà, u   âåêòîð, çàäàþùèé âåëè÷èíó è íàïðàâëåíèå âåêòîðà, k  
êîýôôèöèåíò ñîïðîòèâëåíèÿ. Ïîëîæèì
x = (k, P )   X = {x | k   k   k, P   P   P }.
Îòìåòèì, ÷òî ñêîðîñòü äâèæåíèÿ îáúåêòà îãðàíè÷åíà. Ìàêñèìàëüíàÿ ñêî-
ðîñòü äîñòèãàåòñÿ ïðè  
z 2 = 0, ò.å.
P u   kz2 = 0   z2 = P u
k   P
k .
k , |z2 | = P |u|
Èòàê,
 Z(x) = z = (z1 , z2 ) | |z2 |   w1 (x) = P
k .
Òåïåðü ïîñòðîèì áèíàðíîå îòíîøåíèå R. Ïîëîæèì f = (f 1 , f 2 ), ãäå f 1 =
z2 , f2 = P u kz2 . Îòìåòèì, ÷òî ïðè íàõîæäåíèè âûïóêëîé îáîëî÷êè G(x, z)
äîñòàòî÷íî åå ïîñòðîèòü äëÿ âåêòîðà f 2 = P u   kz 2 , ïîñêîëüêó êîìïîíåíòà
f 1 = z 2 îò ïåðåìåííûõ u è x íå çàâèñèò. Ïîýòîìó âîçüìåì S = {s   E3 | |s| =
1},
  (s, z, x) = max
 (f 2 , s) = max
 (P u   kz2 , s) = P   k(z2 , s).
u :|u |  1
u :| u|  1
Àíàëîãè÷íî äëÿ ñòðàòåãèè x = (k , P )  (s, z, x) = P   k (z2 , s). Îòñþäà
 (x, x , z) = min
 (P   P + (k   k))(z2 , s) = P   P   |k   k||z2 |.
s  S
Çàïèøåì íåðàâåíñòâà (3), çàäàþùèå áèíàðíîå îòíîøåíèå R : xRx  

 
P   P   |k   k||z2 |   0   z : |z2 |   P
k ,

P
k   P
k

 
P   P   |k   k| P
k   0 ,

 (3)
P
k   P
k .
Íàéäåì C(X, R) = {x   X | xRx   x Rx}. Äîêàæåì, ÷òî C(X, R) = {x  
X | P = P }.
Ïóñòü x   X è P < P . Ïîëîæèì x = (k , P + ). Ïðè ìàëîì   > 0 xRx ,
íî x Rx   x /
  C(X, R). Ïóñòü x = (k , P ). Ïîêàæåì, ÷òî x   C(X, R).
Ïóñòü xRx . Òîãäà èç (3) ïîëó÷àåì
P   P   |k   k| P
k   0   P = P , k = k ,
ò.å. èç xRx ñëåäóåò x = x . Ïîýòîìó x Rx è x   C(X, R).
16

Ìîæíî äîêàçàòü, ÷òî ïîñòðîåííîå â äàííîì ïðèìåðå áèíàðíîå îòíîøå-
íèå R íåâîçìîæíî ïðåäñòàâèòü íèêàêèì âåêòîðíûì êðèòåðèåì.
§12. Ìàòåìàòè÷åñêàÿ ìîäåëü îïåðàöèè
Â ýòîì è ñëåäóþùåì ïàðàãðàôàõ èçëàãàåòñÿ ïîäõîä Þ.Á. Ãåðìåéåðà ê
ïîñòðîåíèþ è èññëåäîâàíèþ ìàòåìàòè÷åñêèõ ìîäåëåé îïåðàöèé. Çäåñü ñî-
õðàíåíû îáîçíà÷åíèÿ, èñïîëüçîâàííûå â êíèãå Þ.Á. Ãåðìåéåðà.
Îïåðàöèÿ   ýòî ñîâîêóïíîñòü ìåðîïðèÿòèé, íàïðàâëåííûõ íà äîñòè-
æåíèå íåêîòîðîé öåëè. Ñîâîêóïíîñòü ëèö (èëè îäíî ëèöî), ñòðåìÿùèõñÿ â
îïåðàöèè ê ïîñòàâëåííîé öåëè íàçûâàåòñÿ îïåðèðóþùåé ñòîðîíîé. Â îïåðà-
öèè ìîãóò ó÷àñòâîâàòü äðóãèå ëèöà, íàïðèìåð ïðîòèâíèêè, ïðåñëåäóþùèå
ñîáñòâåííûå öåëè, íå ñîâïàäàþùèå ñ öåëüþ îïåðèðóþùåé ñòîðîíû. Âíóòðè
îïåðèðóþùåé ñòîðîíû âûäåëÿåòñÿ ëèöî, íàçûâàåìîå èññëåäîâàòåëåì îïå-
ðàöèè. Èññëåäîâàòåëü îïåðàöèè ïðåñëåäóåò òó æå öåëü, ÷òî è îïåðèðóþùàÿ
ñòîðîíà. Îäíàêî, îí íå ïðèíèìàåò îêîí÷àòåëüíûõ ðåøåíèé. Åãî çàäà÷à ñî-
ñòîèò â ôîðìèðîâàíèè è èçó÷åíèè ìàòåìàòè÷åñêîé ìîäåëè îïåðàöèè è âû-
ðàáîòêå ðåêîìåíäàöèé ïî âûáîðó ñïîñîáîâ äåéñòâèé (ñòðàòåãèé).
Îïåðèðóþùàÿ ñòîðîíà äëÿ äîñòèæåíèÿ öåëè îïåðàöèè èñïîëüçóåò àê-
òèâíûå ñðåäñòâà (ðåñóðñû). Â êà÷åñòâå ðåñóðñîâ ìîãóò âûñòóïàòü äåíüãè,
ñûðüå, çàïàñû ïðîäóêöèè è ò.ï.
Êîíòðîëèðóåìûå ôàêòîðû   ýòî âåëè÷èíû, âûáîð çíà÷åíèé êîòîðûõ
îïðåäåëÿåò äåéñòâèå îïåðèðóþùåé ñòîðîíû â ðàññìàòðèâàåìîé îïåðàöèè.
Îáû÷íî èìååòñÿ âåêòîð êîíòðîëèðóåìûõ ôàêòîðîâ x   M0 . Çäåñü M0  
ìíîæåñòâî âñåâîçìîæíûõ çíà÷åíèé, êîòîðûå âåêòîð x ìîæåò ïðèíèìàòü â
ïðîöåññå ïðîâåäåíèÿ îïåðàöèè. Âûáîð îïåðèðóþùåé ñòîðîíîé êîíòðîëèðó-
åìûõ ôàêòîðîâ îáû÷íî îñóùåñòâëÿåòñÿ âî âðåìåíè. Ïðè ýòîì ïîñòóïàþùàÿ
èíôîðìàöèÿ îá îáñòàíîâêå, â êîòîðîé ïðîèñõîäèò îïåðàöèÿ, ìîæåò ñóùå-
ñòâåííî ðàñøèðÿòü âîçìîæíîñòè âûáîðà êîíòðîëèðóåìûõ ôàêòîðîâ. Åñëè
âîîáùå íèêàêîé èíôîðìàöèè íå ïîñòóïàåò èëè ïîñòóïàþùàÿ èíôîðìàöèÿ
íå ó÷èòûâàåòñÿ, òî îïåðèðóþùàÿ ñòîðîíà ìîæåò âûáðàòü è ðåàëèçîâàòü
ëþáîé âåêòîð x   M0 . Âåêòîðû x   M0 áóäåì íàçûâàòü ñòðàòåãèÿìè-
êîíñòàíòàìè. Ðàññìîòðèì ïðèìåðû.
Â ìîäåëè "íàïàäåíèå-îáîðîíà" âåêòîð êîíòðîëèðóåìûõ ôàêòîðîâ x ïðè-
íàäëåæèò ìíîæåñòâó
 n
M0 = {x   En |
 xi = A, xi   0, i = 1, ..., n}
i=1
è ïðåäñòàâëÿåò ñîáîé ðàñïðåäåëåíèå ñðåäñòâ íàïàäåíèÿ ïî ïóíêòàì âîçìîæ-
íîãî ïðîðûâà.
Â ìíîãîøàãîâîé àíòàãîíèñòè÷åñêîé èãðå ñ ïîëíîé èíôîðìàöèåé ïåðâûé
èãðîê âûáèðàåò çíà÷åíèÿ êîíòðîëèðóåìûõ ôàêòîðîâ xt , t = 1, ..., T , â òå÷å-
íèå T øàãîâ. Ïðè ýòîì âûáîð àëüòåðíàòèâû xt   Ut (xt 1 , yt 1 ) çàâèñèò îò
ïðåäûñòîðèè èãðû xt  1 , yt 1 ), ò.å. îò âûáîðîâ îáîèõ èãðîêîâ íà ïðåäûäó-
ùèõ øàãàõ. Çäåñü M0 ñîñòîèò èç âñåâîçìîæíûõ çíà÷åíèé, êîòîðûå ìîæåò
ïðèíèìàòü âåêòîð xT = (x1 , ..., xT ). Âûáîð ñòðàòåãèé-êîíñòàíò â ìíîãîøàãî-
17

âîé èãðå ñ ïîëíîé èíôîðìàöèåé âåñüìà îãðàíè÷åí. Íàïðèìåð, íåâîçìîæíî
èãðàòü â øàõìàòû, íå çíàÿ õîäû ïðîòèâíèêà.
Íåêîíòðîëèðóåìûå ôàêòîðû ýòî âåëè÷èíû, âëèÿþùèå íà èñõîä îïåðà-
öèè, íî âûáîð çíà÷åíèé êîòîðûõ íå íàõîäèòñÿ â ðàñïîðÿæåíèè îïåðèðó-
þùåé ñòîðîíû. Íåêîíòðîëèðóåìûå ôàêòîðû äåëÿòñÿ íà íåîïðåäåëåííûå è
ñëó÷àéíûå. Íåîïðåäåëåííûå ôàêòîðû ýòî òàêèå íåêîíòðîëèðóåìûå ôàêòî-
ðû, äëÿ êîòîðûõ èçâåñòíà ëèøü îáëàñòü èõ âîçìîæíûõ çíà÷åíèé. Ïóñòü y  
âåêòîð íåîïðåäåëåííûõ ôàêòîðîâ, y   N0 , ãäå N0   ìíîæåñòâî âñåõ âîçìîæ-
íûõ çíà÷åíèé äëÿ y. Îäíàêî, îïåðèðóþùàÿ ñòîðîíà îáû÷íî ïðåäïîëàãàåò,
÷òî âåêòîð y ïðèíàäëåæèò íåêîòîðîé îáëàñòè íåîïðåäåëåííîñòè N   N0 .
Íàïðèìåð, ïðè àíàëèçå øàõìàòíîé ïàðòèè ìîæíî èñêëþ÷èòü çàâåäîìî ãëó-
ïûå õîäû ïðîòèâíèêà. Ðèñê, ñâÿçàííûé ñ ïðåäïîëîæåíèåì y   N äîëæíà
âçÿòü íà ñåáÿ îïåðèðóþùàÿ ñòîðîíà. Íåîïðåäåëåííûå ôàêòîðû äåëÿòñÿ íà
ñëåäóþùèå:
à) êîíòðîëèðóåìûå ôàêòîðû ïðîòèâíèêà (åãî ñòðàòåãèè),
á) ïðèðîäíûå íåïðåäåëåííîñòè,
â) ôàêòîðû, õàðàêòåðèçóþùèå íåÿñíîñòü öåëè îïåðèðóþùåé ñòîðîíû.
Ïðèâåäåì ïðèìåð ïîñëåäíèõ. Ïóñòü ÷àñòíûå êðèòåðèè Wi (x), i = 1, ..., s
ðàñïîëàãàþòñÿ â ïîðÿäêå íå âîçðàñòàíèÿ âàæíîñòè è â ñâåðòêå F1 (x,  ) =
s
  i Wi (x) îïåðèðóþùàÿ ñòîðîíà íå ðåøàåòñÿ âûáðàòü   = ( 1 , ...,  s )  
i =1
  i = 1,  1    2   ....    s   0}. Òîãäà       = N ìîæíî
  = {  | s
i =1
ðàññìàòðèâàòü êàê íåîïðåäåëåííûé ôàêòîð, õàðàêòåðèçóþùèé íåÿñíîñòü
öåëè îïåðèðóþùåé ñòîðîíû.
Ñëó÷àéíûå ôàêòîðû ýòî ñëó÷àéíûå âåëè÷èíû, âëèÿþùèå íà èñõîä îïå-
ðàöèè. Âåêòîð ñëó÷àéíûõ ôàêòîðîâ îáîçíà÷èì ÷åðåç z   Z. Ïóñòü     çàêîí
ðàñïðåäåëåíèÿ äëÿ z. Îí ìîæåò áûòü òî÷íî íå èçâåñòåí, à èçâåñòíî ëèøü,
÷òî      . Ìíîæåñòâà   âñòðå÷àþòñÿ äâóõ îñíîâíûõ âèäîâ:
1)   = {   ,     L}. Çäåñü òèï çàêîíà ðàñïðåäåëåíèÿ èçâåñòåí (íîðìàëü-
íûé, ýêñïîíåíöèàëüíûé è ò.ï.), íî ïàðàìåòð  , îïðåäåëÿþùèé êîíêðåòíûé
çàêîí, òî÷íî íå èçâåñòåí.
2)   = {   | ai  
 ai (z)d (z)   ai , i = 1, ..., l}. Òèï çàêîíà ðàñïðåäå-
 Z
ëåíèÿ íåèçâåñòåí, íî èçâåñòíû îãðàíè÷åíèÿ íà åãî èíòåãðàëüíûå õàðàêòå-
ðèñòèêè. Íàïðèìåð, åñëè z   E1 , ai (z) = zi , òî   çàäàåò îãðàíè÷åíèÿ íà
ìîìåíòû ñëó÷àéíîé âåëè÷èíû z.
Êðèòåðèé ýôôåêòèâíîñòè. Èñõîä îïåðàöèè áóäåì îòîæäåñòâëÿòü ñ òðîé-
êîé (x, y , z)   M0   N   Z. Ñòåïåíü ñîîòâåòñòâèÿ èñõîäà îïåðàöèè ïîñòàâ-
ëåííîé öåëè çàäàþò ñ ïîìîùüþ êðèòåðèÿ ýôôåêòèâíîñòè F (x, y, z)   ôóíê-
öèè, îïðåäåëåííîé íà M0   N   Z. Êðèòåðèé ýôôåêòèâíîñòè ìàòåìàòè÷åñêè
çàäàåò öåëü îïåðàöèè. Áóäåì ñ÷èòàòü, ÷òî îïåðèðóþùàÿ çàèíòåðåñîâàíà â
óâåëè÷åíèè çíà÷åíèÿ F (x, y, z). Ïðèìåð êðèòåðèÿ ýôôåêòèâíîñòè   ôóíê-
öèÿ âûèãðûøà F (x, y) ïåðâîãî èãðîêà â àíòàãîíèñòè÷åñêîé èãðå.
Ñòðàòåãèÿ. Ìîäåëü îïåðàöèè èññëåäóåòñÿ äî åå ïðîâåäåíèÿ. Áóäåì
óñëîâíî ãîâîðèòü î ìîìåíòå èññëåäîâàíèÿ, ïðåäøåñòâóþùåì íà÷àëó îïå-
18

ðàöèè:
èí ôî ðìà ö èÿ î íå êî íò ð îë èð óåìû õ
ôà êò î ð à õ
 E t
 T
c cc
 T
ìî ìå íò
í à÷ à ëî
 êî íå ö
èñ ñëå äî â à í èÿ
î ï åð àö èè
î ïå ðà ö èè
Âî âðåìÿ ïðîâåäåíèÿ îïåðàöèè ïîñòóïàåò èíôîðìàöèÿ î íåêîíòðîëèðó-
åìûõ ôàêòîðàõ. Èíôîðìàöèîííàÿ ãèïîòåçà   ýòî òî÷íîå îïèñàíèå ïîñòóï-
ëåíèÿ ýòîé èíôîðìàöèè.
Ñòðàòåãèÿ ýòî âûáîð çíà÷åíèé êîíòðîëèðóåìûõ ôàêòîðîâ â çàâèñèìîñòè
îò ïîñòóïàþùåé èíôîðìàöèè î íåêîíòðîëèðóåìûõ ôàêòîðàõ. Ìàòåìàòè÷å-
ñêè ñòðàòåãèÿ çàäàåòñÿ ôóíêöèåé  
x : N   Z > M0 . Ïóñòü M   ìíîæåñòâî
ñòðàòåãèé, îòâå÷àþùèõ èíôîðìàöèîííîé ãèïîòåçå. Ñòðàòåãèÿ âûáèðàåòñÿ
äî íà÷àëà îïåðàöèè â ìîìåíò èññëåäîâàíèÿ.
Ïðèìåðû.
1. Ïóñòü íå îæèäàåòñÿ íèêàêîé èíôîðìàöèè î íåêîíòðîëèðóåìûõ ôàê-
x = x.
òîðàõ. Òîãäà M = M0   ìíîæåñòâî ñòðàòåãèé-êîíñòàíò  
2. Ïóñòü â íà÷àëå îïåðàöèè áóäóò òî÷íî èçâåñòíî çíà÷åíèå y. Òîãäà M =
Mè   ìíîæåñòâî âñåõ ôóíêöèé âèäà  
x : N > M0 .
3. Ïóñòü â íà÷àëå îïåðàöèè áóäóò òî÷íî èçâåñòíû çíà÷åíèÿ y è z. Òîãäà
M =  
M   ìíîæåñòâî âñåõ ôóíêöèé âèäà  
x : N   Z > M0 .
4. Ïóñòü y = (y1 , ..., yn ), à ñëó÷àéíûå ôàêòîðû îòñóòñòâóþò. Ïðåäïî-
 yj . Òîãäà M  
ëîæèì, ÷òî â íà÷àëå îïåðàöèè ïîñòóïèò èíôîðìàöèÿ î n
j =1
 yj ). Çäåñü M0   M   Mè è îáà âêëþ÷åíèÿ  
ìíîæåñòâî ôóíêöèé âèäà f ( n
j =1
ñòðîãèå.
Îêîí÷àòåëüíî ìîäåëü îïåðàöèè çàäàåòñÿ íàáîðîì îáúåêòîâ:
x   M.
F (x, y, z), x   M0 , y   N   N0 , z   Z,      ,  
§13. Îïòèìàëüíûå ñòðàòåãèè â îïåðàöèè.
Êàê ñðàâíèâàòü ñòðàòåãèè? Êàêèå ñòðàòåãèè â îïåðàöèè ñëåäóåò ñ÷èòàòü
îïòèìàëüíûìè? Ïîäõîä Þ.Á.Ãåðìåéåðà ñîñòîèò â ñëåäóþùåì. Ñíà÷àëà äëÿ
êàæäîé ñòðàòåãèè  
x   M îïðåäåëÿåòñÿ îöåíêà ýôôåêòèâíîñòè W(  
x) íà
îñíîâå ïðèíöèïà ãàðàíòèðîâàííîãî ðåçóëüòàòà. Ïî ñìûñëó W ( 
x)   íåêî-
òîðàÿ ãàðàíòèðîâàííàÿ âåëè÷èíà êðèòåðèÿ.
Ïðèìåð. Â èãðå  1 W (x) = min
 F (x, y),
y  Y (x )
ãäå Y (x) = Arg max
 G(x, y) = N. Îòìåòèì, ÷òî ïðèíöèï ãàðàíòèðîâàííî-
y  Y
ãî ðåçóëüòàòà íå èñêëþ÷àåò ýëåìåíòû ðèñêà. Â äàííîì ïðèìåðå ðèñê äëÿ
ïåðâîãî èãðîêà ñîñòîèò â ïðåäïîëîæåíèè, ÷òî âòîðîé èãðîê ìàêñèìèçèðóåò
ñâîþ ôóíêöèþ âûèãðûøà G(x, y) ïðè èçâåñòíîì x.
19

Îïðåäåëåíèå. Ñòðàòåãèÿ  
x0   M íàçûâàåòñÿ îïòèìàëüíîé, åñëè W (  
x0 ) =
max
 W ( 
= Fã(M ). Ïîñëåäíÿÿ âåëè÷èíà íàçûâàåòñÿ íàèëó÷øèì ãàðàíòè-
x)d ef
 
x  M
ðîâàííûì ðåçóëüòàòîì.
Âûâåäåì ôîðìóëó äëÿ îöåíêè ýôôåêòèâíîñòè ñòðàòåãèè. Ñäåëàåì ñëå-
äóþùèå ïðåäïîëîæåíèÿ. Ïóñòü y   ëèáî ïðèðîäíàÿ íåîïðåäåëåííîñòü, ëè-
áî ñòðàòåãèÿ ïðîòèâíèêà, íå çíàþùåãî ðåàëèçàöèè ñëó÷àéíîé âåëè÷èíû z.
Èíòåðåñû ïðîòèâíèêà ëèáî ïðîòèâîïîëîæíû èíòåðåñàì îïåðèðóþùåé ñòî-
ðîíû, ëèáî íå èçâåñòíû. Îïåðèðóþùàÿ ñòîðîíà ðàçðåøàåò îñðåäíåíèå êðè-
òåðèÿ ïî ñëó÷àéíîñòÿì, ò.å. èñïîëüçîâàíèå îñðåäíåííîãî êðèòåðèÿ
=
F (  
 F (  
x(y , z), y , z)d (z).
x, y,  ) de f
 Z
Òîãäà îöåíêà ýôôåêòèâíîñòè èìååò âèä
W (  
x) = inf
 inf
 F ( 
x(y , z), y , z)d (z) = inf
 inf
 F ( 
x, y,  ). (1)
y  N
     
y  N
    
 Z
Èòàê, ñíà÷àëà ïðîèçâîäèòñÿ îñðåäíåíèå êðèòåðèÿ ýôôåêòèâíîñòè F ( 
x(y , z), y , z)
ïî  , à ïîòîì áåðåòñÿ íèæíÿÿ ãðàíü ïî îñòàâøèìñÿ íåîïðåäåëåííîñòÿì y è
 . Ýòî ïðèìåð èñïîëüçîâàíèÿ ïðèíöèïà ãàðàíòèðîâàííîãî ðåçóëüòàòà. Îò-
ìåòèì, ÷òî åñëè áû ïðîòèâíèê çíàë ðåàëèçàöèþ ñëó÷àéíîé âåëè÷èíû z, òî
ôîðìóëà äëÿ îöåíêè ýôôåêòèâíîñòè áûëà áû äðóãîé:
W (  
x) = inf
 inf
 F ( 
x(y , z), y , z)d (z).
    
y N
 Z
Äåéñòâèòåëüíî, â õóäøåì ñëó÷àå ïðîòèâíèê çíàåò ñòðàòåãèþ  
x è â ñîñòîÿíèè
íàéòè inf
 F ( 
x(y , z), y , z) ïðè èçâåñòíîì åìó z.
y N
Ïîêàæåì, ÷òî
 W ( 
x)   W (  
x).
Äëÿ        è  y   N
 F ( 
x(y, z), y, z)d (z)  
 inf
 F ( 
x(y , z), y , z)d (z)
y N
Z
 Z
Îòñþäà
 inf
 F ( 
x(y , z), y , z)d (z)  
 inf
 F (  
x(y, z), y, z)d (z)
y  N
y  N
 Z
 Z
Âçÿâ inf
 îò ëåâîé è ïðàâîé ÷àñòè, ïîëó÷èì íåðàâåíñòâî
    
W ( 
x)   W (  
x).
20

Îòìåòèì, ÷òî ýòî íåðàâåíñòâî îòðàæàåò âîçðîñøóþ èíôîðìèðîâàííîñòü
ïðîòèâíèêà.
Ïåðåéäåì ê èñïîëüçîâàíèþ ñìåøàííûõ ñòðàòåãèé. Ïðåäïîëîæèì, ÷òî
íå îæèäàåòñÿ íèêàêîé èíôîðìàöèè î íåêîíòðîëèðóåìûõ ôàêòîðàõ. Â ýòîì
ñëó÷àå îïåðèðóþùàÿ ñòîðîíà èñïîëüçóåò ñòðàòåãèè-êîíñòàíòû  
x = x   M =
M0 . Åñëè íàèëó÷øèé ãàðàíòèðîâàííûé ðåçóëüòàò Fã(M0 ) åå íå óñòðàèâàåò,
òî ìîæíî èñïîëüçîâàòü ñìåøàííûå ñòðàòåãèè. Íàïîìíèì, ÷òî ñìåøàííàÿ
ñòðàòåãèÿ   åñòü âåðîÿòíîñòíîå ðàñïðåäåëåíèå íà M0 . Îïðåäåëèì óñëîâèÿ
ïðèìåíåíèÿ ñìåøàííîé ñòðàòåãèè. Ê ñôîðìóëèðîâàííûì âûøå ïðåäïîëî-
æåíèÿì äîáàâèì åùå îäíî: ïðîòèâíèê íå äîëæåí çíàòü ðåàëèçàöèè x   M0 .
Òîãäà îöåíêà ýôôåêòèâíîñòè ñìåøàííîé ñòðàòåãèè   èìååò âèä
W( ) = inf
 inf
 F (x, y, z)d (x)d (z). (2)
y  N
     
 Z M 0
Åñëè áû ïðîòèâíèê çíàë ðåàëèçàöèþ z, òî ôîðìóëà áûëà áû äðóãîé
W ( ) = inf
 inf
 F(x, y , z)d (x)d (z).
     
y  N
 Z
M 0
 W( ) ÿâëÿåòñÿ íàèëó÷øèì ãàðàíòèðîâàííûì ðåçóëü-
Âåëè÷èíà Fc = sup
  {  }
òàòîì â ñìåøàííûõ ñòðàòåãèÿõ.
Âåðíåìñÿ ê îïðåäåëåíèþ îïòèìàëüíîé ñòðàòåãèè  
 W ( 
x) =
x0 : W ( 
x0 ) = max
 
x  M
Fã(M ). Åñëè ïîñëåäíèé ìàêñèìóì íå äîñòèãàåòñÿ, òî èñïîëüçóþò ïîíÿòèå
 -îïòèìàëüíîé ñòðàòåãèè.
Îïðåäåëåíèå. Ïóñòü çàäàíî   > 0. Ñòðàòåãèÿ  
x    M íàçûâàåòñÿ  -
îïòèìàëüíîé, åñëè W ( 
 W(  
x)    .
x  )   sup
 
x  M
Çàäà÷à ïîèñêà âåëè÷èíû Fã(M ) íåïðîñòàÿ, ïîñêîëüêó îíà ñîñòîèò â ìàê-
ñèìèçàöèè W(  
x) íà ìíîæåñòâå ôóíêöèé M. Ýòà çàäà÷à óïðîùàåòñÿ, åñëè âî
ìíîæåñòâå ñòðàòåãèé M ñîäåðæàòñÿ àáñîëþòíî îïòèìàëüíûå ñòðàòåãèè.
Äî êîíöà ýòîãî ïàðàãðàôà áóäåì ïðåäïîëàãàòü èçâåñòíûì çàêîí ðàñïðåäå-
ëåíèÿ ñëó÷àéíûõ ôàêòîðîâ  .
Îïðåäåëåíèå. Ñòðàòåãèÿ  
xa   M íàçûâàåòñÿ àáñîëþòíî îïòèìàëüíîé,
åñëè
 F (  
 F ( 
x, y,  )   y   N.
xa, y,  ) = max
 
x  M
Òåîðåìà 3.4. Ïóñòü ñóùåñòâóåò àáñîëþòíî îïòèìàëüíàÿ ñòðàòåãèÿ  
xa  
M. Òîãäà  
xa   îïòèìàëüíàÿ ñòðàòåãèÿ è
Fã(M ) = inf
 max
 F ( 
x, y,  ).
y  N
 
x  M
Äîêàçàòåëüñòâî. Äëÿ ëþáîé ñòðàòåãèè  
x   M èìååì
W ( 
x) = inf
 F ( 
x, y,  )   inf
 max
 F (  
x, y,  ) =
y N
y N
 
x  M
21

= inf
 F ( 
xa , y,  ) = W (  
xa ).
y N
Ñëåäñòâèå. 1) Ïóñòü äëÿ ëþáûõ y   N äîñòèãàåòñÿ max
 F(x, y ,  ). Òîãäà
x  M0
= Fã(Mè) = inf
 max
 F (x, y,  ).
Fè de f
y N
x  M0
2) Ïóñòü äëÿ ëþáûõ y   N, z   Z äîñòèãàåòñÿ max
 F(x, y , z). Òîãäà
x  M0
 
= Fã(  
M) = inf
 max
 F (x, y , z)d (z).
F de f
y  N
x  M 0
 Z
Çàìå÷àíèå. Ôîðìóëû äëÿ Fè è  
F íå ñîäåðæàò ñèìâîëîâ îïòèìèçàöèè ïî
ìíîæåñòâó ôóíêöèé.
Äîêàçàòåëüñòâî. 1). Îïðåäåëèì ñòðàòåãèþ  
xa èç ñëåäóþùåãî óñëîâèÿ:
 
 F (x, y,  ) ïðè ëþáîì y   N. Ñòðàòåãèÿ  
xa (y)   Arg max
xa ñîäåðæèòñÿ âî
x  M 0
ìíîæåñòâå ñòðàòåãèé Mè. Ïîêàæåì, ÷òî îíà àáñîëþòíî îïòèìàëüíà. Äåé-
ñòâèòåëüíî, äëÿ ëþáîé ñòðàòåãèè  
x   Mè è ëþáîì y   N
F ( 
x, y,  ) = F (  
x(y), y,  )   max
 F (x, y,  )
x  M 0
è ðàâåíñòâî çäåñü äîñòèãàåòñÿ íà ñòðàòåãèè  
xa . Ïî òåîðåìå 3.4
Fè = inf
 max
 F ( 
x, y,  ) = inf
 max
 F (x, y,  ).
y  N
 
x  M
y  N
x  M0
2) Îïðåäåëèì ñòðàòåãèþ  
xa èç ñëåäóþùåãî óñëîâèÿ:
 
 F(x, y , z)
xa (y, z)   Arg max
x M 0
ïðè ëþáûõ y   N, z   Z. Ñòðàòåãèÿ  
xa ñîäåðæèòñÿ âî ìíîæåñòâå ñòðàòåãèé
 
M . Ïîêàæåì, ÷òî îíà àáñîëþòíî îïòèìàëüíà. Äåéñòâèòåëüíî, äëÿ ëþáûõ
 
x    
M è y   N
F ( 
x, y,  ) =
 F (  
x(y, z), y, z)d (z)  
 max
 F (x, y, z)d (z) =
x  M 0
 Z
 Z
=
 F ( 
xa (y, z), y, z)d (z) = F ( 
xa , y ,  ).
 Z
Ïî òåîðåìå 3.4
 
F = inf
 max
 F ( 
x, y,  ) = inf
 max
 F(x, y , z)d (z).
y N
y N
 
x    
M
x  M0
 Z
22

Ïóñòü äëÿ ìíîæåñòâà ñòðàòåãèé M ïðè íåêîòîðîì y   N max
 F ( 
x, y,  )
 
x  M
íå äîñòèãàåòñÿ, íî sup
 F(  
x, y ,  ) < + . Òîãäà ìîæíî ââåñòè ïîíÿòèå  -
 
x  M
àáñîëþòíî îïòèìàëüíîé ñòðàòåãèè.
Îïðåäåëåíèå. Ïóñòü çàäàíî   > 0. Ñòðàòåãèÿ  
x 
a   M íàçûâàåòñÿ  -
àáñîëþòíî îïòèìàëüíîé, åñëè
F(  
 F (  
x, y,  )    ,   y   N.
x 
a (y, z), y,  )   sup
 
x  M
Ðàññìîòðèì ïðèìåð ìíîæåñòâà ñòðàòåãèé, íå ñîäåðæàùèõ  -àáñîëþòíî îï-
òèìàëüíûå ñòðàòåãèè.
Ïðèìåð. Ïóñòü M = M0 = {1, 2}, N = {1, 2}, à z îòñóòñòâóåò. Êðèòåðèé
ýôôåêòèâíîñòè çàäàäèì ìàòðèöåé
(F(i, j))2  2 =  1 1
1  1 , i   M0 , j   N.
Äîêàæåì, ÷òî ïðè 0     < 2 â M0 íå ñóùåñòâóåò  -àáñîëþòíî îïòèìàëüíîé
ñòðàòåãèè. Âîçüìåì i = 1. Òîãäà F (1, 1) =  1 < 1     = F (2, 1)    , ò.å. ïðè
j = 2 íàðóøàåòñÿ íåðàâåíñòâî èç îïðåäåëåíèÿ  -àáñîëþòíî îïòèìàëüíîé
ñòðàòåãèè. Èòàê, äîêàçàíî, ÷òî ñòðàòåãèÿ i = 1 íå ÿâëÿåòñÿ  -àáñîëþòíî
îïòèìàëüíîé. Àíàëîãè÷íî äîêàçûâàåòñÿ, ÷òî ñòðàòåãèÿ i = 2 òàêæå íå  -
àáñîëþòíî îïòèìàëüíà.
Òåîðåìà 3.4 . Ïóñòü äëÿ âñÿêîãî   > 0 ñóùåñòâóåò  -àáñîëþòíî îïòè-
ìàëüíàÿ ñòðàòåãèÿ  
x 
x 
a   M. Òîãäà ñòðàòåãèÿ  
a  -îïòèìàëüíà è
Fã(M) = inf
 sup
 F ( 
x, y,  ).
y N
 
x  M
Äîêàæèòå ñàìîñòîÿòåëüíî.
Ñëåäñòâèå. 1) Ïóñòü äëÿ ëþáûõ y   N âåëè÷èíà sup
 F (x, y,  ) êîíå÷-
x  M 0
íàÿ. Òîãäà
= Fã(Mè) = inf
 sup
 F (x, y,  ).
 Fè de f
y N
x  M0
2) Ïóñòü äëÿ ëþáûõ y   N, z   Z âåëè÷èíà max
 F (x, y, z) êîíå÷íàÿ.
x  M 0
Òîãäà
  
= Fã(  
M) = inf
 sup
 F (x, y , z)d (z).
F de f
y  N
x  M 0
 Z
Äîêàæèòå ñàìîñòîÿòåëüíî.
Çàêîí÷èì ïàðàãðàô ñðàâíåíèåì íàèëó÷øèõ ãàðàíòèðîâàííûõ ðåçóëüòà-
òîâ äëÿ ÷åòûðåõ ìíîæåñòâ ñòðàòåãèé : M0 , { }, Mè è  
M . Ïîëîæèì F 0
ã =
Fã(M0 ). Ðàíåå ââåëè âåëè÷èíû
 W( ), Fè = Fã(Mè),  
F = Fã(  
M ).
Fc = sup
  {  }
23

Òåîðåìà 3.5. Ñïðàâåäëèâû íåðàâåíñòâà
F .
F 0
ã   Fc   Fè    
Ïðåäïîëîæèì, ÷òî ñëó÷àéíûé ôàêòîð z îòñóòñòâóåò, M0 è N   ïàðàëëåëå-
ïèïåäû åâêëèäîâûõ ïðîñòðàíñòâ, à êðèòåðèé F(x, y ) íåïðåðûâåí íà M0  N.
Òîãäà, åñëè F âîãíóò ïî x, òî F 0
ã = Fc , à åñëè F ÿâëÿåòñÿ âûïóêëûì ïî y ,
òî Fc = Fè.
Äîêàçàòåëüñòâî. Íàïîìíèì, ÷òî çàêîí ðàñïðåäåëåíèÿ ñëó÷àéíûõ ôàêòî-
ðîâ   ïðåäïîëàãàåòñÿ èçâåñòíûì. Èìååì
 inf
 F (x, y,  )   sup
 inf
 F(x, y ,  )d (x) = Fc ,
ã = sup
F 0
y  N
y  N
   { }
x  M 0
M 0
ïîñêîëüêó M0   { }. Äàëåå, äëÿ ëþáîé ñìåøàííîé ñòðàòåãèè     { }
W ( ) = inf
 F (x, y,  )d (x)   inf
 sup
 F (x, y,  ) = Fè.
y N
y N
x  M 0
 M0
F âûòåêàåò èç âêëþ÷åíèÿ ìíîæåñòâ
Îòñþäà Fc   Fè. Íåðàâåíñòâî Fè    
ñòðàòåãèé: Mè    
M.
Ïóñòü ñëó÷àéíûé ôàêòîð z îòñóòñòâóåò. Ðàññìîòðèì íåïðåðûâíóþ èãðó
  = M0 , N, F (x, y) , â êîòîðîé
 min
 min
 F(x, y )d (x) = v
 F(x, y ), Fc = max
ã = v = max
F 0
y  N
y  N
   { }
x  M 0
M 0
  çíà÷åíèå èãðû, Fè = v = min
 max
 F (x, y). Òåïåðü âñå óòâåðæäåíèÿ âûòå-
y  N
x  M0
êàþò èç òåîðåì 1.14, 1.15.
Ðåçóëüòàòàì äîêàçàííîé òåîðåìû ìîæíî ïðèäàòü èíôîðìàöèîííûé ñìûñë.
ã ìîæíî ðàññìàòðèâàòü êàê öåííîñòü èíôîðìàöèè
Âåëè÷èíó Öï = Fc   F 0
ïðîòèâíèêà î çíà÷åíèè x. Ïîêàæåì, ÷òî åñëè ïðîòèâíèê çíàåò x, òî îïå-
ðèðóþùàÿ ñòîðîíà îáåñïå÷èâàåò ñåáå ðåçóëüòàò F0
ã . Îöåíêà ýôôåêòèâíîñòè
ëþáîé ñìåøàííîé ñòðàòåãèè  
W( ) =
 min
 F(x, y )d (x)
y  N
 M0
íå ïðåâîñõîäèò
 max
 min
 F (x, y) = F 0
ã .
y  N
x  M 0
Ïîýòîìó â ýòîì ñëó÷àå ïðèìåíåíèå ñìåøàííûõ ñòðàòåãèé íå èìååò ñìûñëà,
à èñïîëüçîâàíèå ÷èñòûõ ñòðàòåãèé ïîçâîëÿåò ïîëó÷èòü F 0
ã . Åñëè, íàîáîðîò,
ðåàëèçàöèÿ çíà÷åíèÿ x ïðîòèâíèêó íåèçâåñòíà, òî îïåðèðóþùàÿ ñòîðîíà
ìîæåò ïîëó÷èòü ðåçóëüòàò Fc . Åñëè êðèòåðèé F (x, y) âîãíóò ïî x, òî Öï = 0
è ïðîòèâíèêó íå èìååò ñìûñëà äîáèâàòüñÿ èíôîðìàöèè î x.
24

Àíàëîãè÷íî âåëè÷èíó Öo = Fè   Fc ìîæíî ðàññìàòðèâàòü êàê öåííîñòü
èíôîðìàöèè îïåðèðóþùåé ñòîðîíû î çíà÷åíèè y . Äåéñòâèòåëüíî, åñëè èí-
ôîðìàöèÿ î íåîïðåäåëåííîì ôàêòîðå y îæèäàåòñÿ, òî îïåðèðóþùàÿ ñòî-
ðîíà ïîëó÷àåò ðåçóëüòàò Fè, à â ïðîòèâíîì ñëó÷àå   Fc . Åñëè êðèòåðèé
F (x, y) ÿâëÿåòñÿ âûïóêëûì ïî y, òî Öo = 0 è îïåðèðóþùåé ñòîðîíå íå
èìååò ñìûñëà äîáèâàòüñÿ èíôîðìàöèè îá y .
Ðàññìîòðèì ïðèìåð ïîèñêà îïòèìàëüíûõ è àáñîëþòíî-îïòèìàëüíûõ ñòðà-
òåãèé. Ïóñòü i   M0 = {1, 2, 3}, j   N = {1, 2, 3, 4}, ñëó÷àéíûé ôàêòîð z
îòñóòñòâóåò. Êðèòåðèé ýôôåêòèâíîñòè çàäàåòñÿ ìàòðèöåé

 1 2 5 2
 
  .
3 2  1 2
4 2 3 1
(F (i, j))3  4 =
a) M = Mè   ìíîæåñòâî âñåõ ôóíêöèé âèäà  i : N > M0 . Âñåãî 81
ñòðàòåãèÿ. Çäåñü ïî ñëåäñòâèþ òåîðåìû 3.4
Fè = Fã(Mè) = min
 max
 F (i, j) = 2.
1  j  4
1   i  3
Ñòðàòåãèÿ  i0 îïòèìàëüíà, åñëè min
 F ( i0 (j), j) = 2 èëè F( 
i0 (j), j)   2,   j  
1  i  3
N. Ïåðå÷èñëèì âîçìîæíûå çíà÷åíèÿ îïòèìàëüíîé ñòðàòåãèè:  
i0 (1) = 2, 3,  i0 (2) =
1, 2, 3,  i0 (3) = 1, 3,  i0 (4) = 1, 2. Ïîä÷åðêíóòûå çíà÷åíèÿ îòâå÷àþò îäíîé
êîíêðåòíîé îïòèìàëüíîé ñòðàòåãèè. Âñåãî 2 · 3 · 2 · 2 = 24 îïòèìàëüíûå
ñòðàòåãèè.
Íàéäåì âñå àáñîëþòíî-îïòèìàëüíûå ñòðàòåãèè
 ia : F( ia(j), j) = max
 F (i, j).
i  M 0
Ïåðå÷èñëèì âîçìîæíûå çíà÷åíèÿ àáñîëþòíî-îïòèìàëüíîé ñòðàòåãèè:  ia (1) =
3,  
ia (2) = 1, 2, 3,  ia(3) = 1,  ia(4) = 1, 2. Âñåãî 6 àáñîëþòíî-îïòèìàëüíûõ
ñòðàòåãèé.
á) Ïóñòü â íà÷àëå îïåðàöèè îïåðèðóþùåé ñòîðîíå áóäåò èçâåñòíî, êàêî-
ìó èç ìíîæåñòâ N1 = {1, 2} èëè N2 = {3, 4} ïðèíàäëåæèò çíà÷åíèå íåîïðå-
äåëåííîãî ôàêòîðà j. Çäåñü ñòðàòåãèÿ èìååò âèä
 i(j) = i1 , j   N1 ,
i2 , j   N2 .
Ìíîæåñòâî M ñîñòîèò èç 9 ñòðàòåãèé. Â íåì ñîäåðæèòñÿ àáñîëþòíî-îï-
òèìàëüíàÿ ñòðàòåãèÿ  ia : ia
2 = 1. Ñëåäîâàòåëüíî, ïî òåîðåìå 3.4
1 = 3, ia
Fã(M ) = 2. Ìíîæåñòâî M ñîäåðæèò 2 îïòèìàëüíûå ñòðàòåãèè: i0
1 = 2, 3, i0
2 =
1.
 §14. Íåîáõîäèìûå óñëîâèÿ äëÿ îïòèìàëüíûõ ñòðàòåãèé.
Ðàññìîòðèì îïåðàöèþ áåç ñëó÷àéíûõ ôàêòîðîâ è ìíîæåñòâîì ñòðàòåãèé
M = M0 . Â ýòîì ñëó÷àå îïòèìàëüíàÿ ñòðàòåãèÿ x0   M0 ÿâëÿåòñÿ ìàêñè-
ìèííîé:
 W (x), ãäå W(x) = min
 F (x, y).
 W (x0 ) = max
y  N
x  M 0
25

Ïîèñê ìàêñèìèííûõ è ìèíèìàêñíûõ ñòðàòåãèé ó íàñ âñòðå÷àëñÿ ïðè ðåøå-
íèè àíòàãîíèñòè÷åñêèõ èãð.
Íàéäåì íåîáõîäèìûå óñëîâèÿ äëÿ ìàêñèìèííûõ ñòðàòåãèé è îáñóäèì
ìåòîä èõ ïîèñêà. Íåîáõîäèìûå óñëîâèÿ áóäóò èñïîëüçîâàòü ôîðìóëó äëÿ
ïðîèçâîäíîé ïî íàïðàâëåíèþ ôóíêöèè ìèíèìóìà W(x).
Íàïîìíèì îïðåäåëåíèå ïðîèçâîäíîé ïî íàïðàâëåíèþ ôóíêöèè ìíîãèõ
ïåðåìåííûõ. Ïóñòü â åâêëèäîâîì ïðîñòðàíñòâå Em çàäàíà ôóíêöèÿ h(x).
Âîçüìåì âåêòîð     Em, çàäàþùèé íàïðàâëåíèå â Em.
Îïðåäåëåíèå. Âåëè÷èíà
 h(x +   )   h(x)
 de f
lim
= dh(x)
 
d 
  > +0
íàçûâàåòñÿ ïðîèçâîäíîé ôóíêöèè h(x) ïî íàïðàâëåíèþ   â òî÷êå x.
Êàê èçâåñòíî èç êóðñà ìàòåìàòè÷åñêîãî àíàëèçà, åñëè ôóíêöèÿ h(x)
äèôôåðåíöèðóåìà â Em , òî
 m
dh(x)
 (x) = ( , h (x))
  i hxi
d  =
i =1
  ñêàëÿðíîå ïðîèçâåäåíèå âåêòîðà   íà ãðàäèåíò h (x) â òî÷êå x.
Ôóíêöèÿ h(x) ìîæåò íå áûòü äèôôåðåíöèðóåìîé â òî÷êå x0 , íî èìåòü
â ýòîé òî÷êå ïðîèçâîäíóþ ïî íàïðàâëåíèþ.
Ïðèìåð. Ïóñòü h(x) = min[f (x), g(x)], ãäå x   E1 , ôóíêöèè f (x) è
g(x) äèôôåðåíöèðóåìû, èõ ãðàôèêè ïåðåñåêàþòñÿ â òî÷êå x0 è f (x0 ) >
0, g (x0 ) < 0 (ðèñ. 14.1).
T
f (x)
g(x)
 x
 E
 x0
Ðèñ. 14.1.
Ôóíêöèÿ h(x0 ) íå äèôôåðåíöèðóåìà. Â òî÷êå x0 ñóùåñòâóþò äâà íà-
ïðàâëåíèÿ, çàäàâàåìûå âåêòîðàìè   = (1) è   .
Óïðàæíåíèå. Ïîêàæèòå, ÷òî
dh(x0 )
d  = g (x0 ), dh(x0 )
d(  ) =  f (x0 ).
26

Òåîðåìà 3.6. Ïóñòü x   D   Em , ãäå D   îòêðûòîå ìíîæåñòâî â Em ,
à y ïðèíàäëåæèò ìåòðè÷åñêîìó êîìïàêòó N. Ïðåäïîëîæèì, ÷òî ôóíêöèè
F (x, y), Fxi (x, y), i = 1, ..., m îïðåäåëåíû è íåïðåðûâíû íà D   N. Òîãäà â
ëþáîé òî÷êå x   D ïî ëþáîìó íàïðàâëåíèþ     Em ñóùåñòâóåò ïðîèçâîä-
íàÿ ôóíêöèè ìèíèìóìà W (x), êîòîðàÿ èìååò âèä
 m
dW (x)
 (x, y), (1)
  i Fx i
d  = min
y  N (x)
i =1
ãäå N(x) = Arg min
 F (x, y).
y  N
Çàìå÷àíèå. Ôîðìóëà (1) ïîêàçûâàåò, ÷òî, ñ íåêîòîðîé îãîâîðêîé, îïåðà-
öèè âçÿòèÿ ìèíèìóìà è ïðîèçâîäíîé ïî íàïðàâëåíèþ ïåðåñòàíîâî÷íû. Â
ïðàâîé ÷àñòè ôîðìóëû (1) âìåñòî N ôèãóðèðóåò N(x).
Äîêàçàòåëüñòâî. Çàìåòèì, ÷òî N(x)   êîìïàêò êàê çàìêíóòîå ïîäìíî-
æåñòâî êîìïàêòà N. Ðàññìîòðèì x   D è ïðîèçâîëüíûé âåêòîð     Em .
Ïóñòü xk = x +  k  ,  k > 0, lim
  k = 0   ïîñëåäîâàòåëüíîñòü âåêòîðîâ,
k > 
ñõîäÿùàÿñÿ ê x. Çàïèøåì ïîñëåäíèå ðàâåíñòâà âåêòîðîâ â êîîðäèíàòàõ:
xk
i   xi =  k i , i = 1, ..., m, k = 1, 2, ... Íåîáõîäèìî äîêàçàòü ñóùåñòâîâàíèå
ïðåäåëà
 W (xk )   W (x)
 lim
 ,
 k
k >  
çàäàâàåìîãî ôîðìóëîé (1). Ðàññìîòðèì ïîñëåäîâàòåëüíîñòü yk   N (xk ), k =
1, 2, ... è ëþáîå y   N(x). Òîãäà
W (xk )   W (x)
 =
 = F (xk , yk )   F (x, y)
 k
 k
  
= F (xk , y k )   F(xk , y ) + F(xk , y )   F(x, y )
 k
 m
 (x +  k (xk   x), y)
 (xk
i   xi )Fxi
i =1
 =
 =
  F (xk , y)   F (x, y)
 k
 k
 m
=
  i Fxi (x +  k(xk   x), y),
i=1
 (x, y), ïî-
ãäå 0 <  k < 1. Îòñþäà, ïîëüçóÿñü íåïðåðûâíîñòüþ ôóíêöèé Fxi
ëó÷èì îöåíêó äëÿ âåðõíåãî ïðåäåëà
 m
 W(xk )   W (x)
lim
  
  i Fxi (x, y),   y   N(x).
 k
k>  
i =1
Îòñþäà
 m
 W(xk )   W (x)
 lim
   min
  i Fx i (x, y). (2)
 k
k >  
y N ( x)
i= 1
27

Äëÿ çàâåðøåíèÿ äîêàçàòåëüñòâà äîñòàòî÷íî óñòàíîâèòü àíàëîãè÷íîå íåðà-
âåíñòâà äëÿ íèæíåãî ïðåäåëà:
 m
 W(xk )   W (x)
lim
   min
 (x, y). (3)
  i Fx i
 k
y N ( x)
k >  
i= 1
Ïî îïðåäåëåíèþ íèæíåãî ïðåäåëà ñóùåñòâóåò òàêàÿ ïîäïîñëåäîâàòåëüíîñòü
kl , l = 1, 2, ..., ÷òî
 W(xkl )   W(x)
 W (xk )   W (x)
lim
 = lim
 .
 k
l >  
 kl
k >  
Â ñèëó êîìïàêòíîñòè ìíîæåñòâà N áåç ïîòåðè îáùíîñòè ìîæíî ñ÷èòàòü, ÷òî
lim
 ykl = y    N. Ïîêàæåì, ÷òî y    N(x). Äåéñòâèòåëüíî, F(xkl , ykl )  
l>  
F (xkl , y),   y   N. Ïåðåõîäÿ â ýòîì íåðàâåíñòâå ê ïðåäåëó ïðè l >  ,
ïîëó÷èì F (x, y )   F(x, y ),   y   N   y    N(x). Äàëåå, èìååì
W (xkl )   W(x)
 =
 = F (xkl , ykl )   F (x, y )
 kl
 kl
  
= F (xk l , y kl )   F (x, yk l ) + F (x, ykl )   F (x, y )
 kl
 m
 (xk l
i   xi )Fxi (x +  kl (xk l   x), yk l )
 =
 =
i =1
  F (xkl , ykl )   F (x, ykl )
 k l
 k l
 m
=
 (x +  kl (xkl   x), ykl ),
  i Fx i
i =1
ãäå 0 <  kl < 1. Ïåðåéäåì â ïîëó÷åííîì íåðàâåíñòâå ê ïðåäåëó ïðè l >  
è ïîëó÷èì
 m
 m
 W (xk )   W (x)
lim
  
 (x, y).
 (x, y  )   min
  i Fx i
  i Fx i
 k
y  N (x )
k>  
i= 1
i =1
Íåðàâåíñòâî (3) äîêàçàíî. Óòâåðæäåíèå òåîðåìû ñëåäóåò èç íåðàâåíñòâ (2)
è (3), êîòîðûå ìîãóò âûïîëíÿòüñÿ òîëüêî êàê ðàâåíñòâà.
Ïðèìåð. Ðàññìîòðèì â E3 ôóíêöèþ
W (x1 , x2 , x3 ) = min
  j (x1 , x2 , x3 ),
1  j  3
ãäå  1 = x2
1 ) + x2 + 10x3 .
1 + x2
2 + x2
2 ,  3 = cos( x2
3 ,  2 = x1 0
Íàéäåì ïðîèçâîäíóþ ôóíêöèè W (x) â òî÷êå x0 = (2,  2, 1) ïî íàïðàâëå-
íèþ   = ( 3, 2,  1). Çäåñü ìîæíî âîñïîëüçîâàòüñÿ ôîðìóëîé (1), ïîñêîëüêó
ìíîæåñòâî N = {1, 2, 3} ïðåâðàòèòü â ìåòðè÷åñêîå ïðîñòðàíñòâî, çàäàâ íà
28

íåì ìåòðèêó. Èìååì  1 (x0 ) = 9,  2 (x0 ) = 21 0 ,  3 (x0 ) = cos(4 )   2 + 10 = 9.
Îòñþäà N(x0 ) = {1, 3}. Äàëåå
 1 (x0 ) = (4,  4, 2),  3 (x0 ) = (0, 1, 10),
( ,  1 (x0 )) =  22, ( ,  3 (x0 )) =  8   dW (x0 )
d  =  22.
Ïåðåéäåì ê âûâîäó íåîáõîäèìûõ óñëîâèé äëÿ ìàêñèìèííîé ñòðàòåãèè.
Ñëåäñòâèå òåîðåìû 3.6. Ïóñòü M0   âûïóêëûé êîìïàêò â Em, à L(x0 )
  ìíîæåñòâî äîïóñòèìûõ íàïðàâëåíèé â òî÷êå x0   M0 ,
å x0   M0   ìàêñèìèííàÿ ñòðàòåãèÿ. Òîãäà â óñëîâèÿõ òåîðåìû 3.6
âûïîëíåíî ñëåäóþùåå íåîáõîäèìîå óñëîâèå:
 m
sup
 min
 (x0 , y)   0. (4).
  i Fx i
y N (x0 )
   L (x0 )
i= 1
Äîêàçàòåëüñòâî. Ôóíêöèÿ W (x) äîñòèãàåò â òî÷êå x0   M0 íàèáîëüøåãî
çíà÷åíèÿ. Ïîýòîìó
dW (x0 )
 W(x0 +   )   W (x0 )
d  = lim
    0       L(x0 ),
  > +0
ïîñêîëüêó ïðè ìàëûõ   > 0 âåêòîð x0 +   ïðèíàäëåæèò M0 ïî îïðåäåëåíèþ
äîïóñòèìîãî íàïðàâëåíèÿ  .
Òåïåðü çàéìåìñÿ óïðîùåíèåì óñëîâèÿ (4) äëÿ ÷àñòíûõ ñëó÷àåâ. Ïóñòü
M0 = [a, b]   îòðåçîê.
Òåîðåìà 3.7. Ïóñòü ôóíêöèè F (x, y), Fx (x, y) íåïðåðûâíû íà ìíîæåñòâå
D   N, ãäå D   èíòåðâàë, ñîäåðæàùèé îòðåçîê M0 = [a, b], à N   êîìïàêò
ìåòðè÷åñêîãî ïðîñòðàíñòâà. Òîãäà äëÿ ìàêñèìèííîé ñòðàòåãèè x0   M0
âûïîëíåíî õîòÿ áû îäíî èç ñëåäóþùèõ òðåõ óñëîâèé:
à) x0 = a èëè x0 = b;
 F (x, y);
á) íàéäóòñÿ y1 = y2   N (x0 ) = Arg min
y N
â) N(x0 ) = {y1 } è Fx (x0 , y1 ) = 0.
Çàìå÷àíèå. Òåîðåìà îáîáùàåò íåîáõîäèìûå óñëîâèÿ äëÿ òî÷êè ìàêñè-
ìóìà x0 äèôôåðåíöèðóåìîé ôóíêöèè íà îòðåçêå: ëèáî òî÷êà x0 ÿâëÿåòñÿ
êîíöîì îòðåçêà, ëèáî ïðîèçâîäíàÿ ôóíêöèè â òî÷êå x0 ðàâíà íóëþ.
Äîêàçàòåëüñòâî. Ïóñòü x0   îïòèìàëüíàÿ ñòðàòåãèÿ. Åñëè âûïîëíåíû
óñëîâèÿ 1) èëè 2), òî âñå äîêàçàíî. Ïóñòü óñëîâèÿ 1) è 2) íå âûïîëíåíû, ò.å.
a < x0 < b è N(x0 ) = {y1 }. Ïîêàæåì, ÷òî îáÿçàòåëüíî âûïîëíåíî óñëîâèå
3). Èç ôîðìóëû (4) ñëåäóåò, ÷òî äëÿ äâóõ äîïóñòèìûõ íàïðàâëåíèé   = (1)
è    âûïîëíåíû íåðàâåíñòâà
dW (x0 )
d  = 1 · Fx (x0 , y1 )   0, dW (x0 )
d(  ) = ( 1) · Fx (x0 , y1 )   0.
29

Ñëåäîâàòåëüíî, Fx (x0 , y1 ) = 0.
Ñëåäñòâèå. Ïóñòü â óñëîâèÿõ òåîðåìû 3.7
N = {y   En | cj   yj   dj , j = 1, ..., n}
  ïàðàëëåëåïèïåä åâêëèäîâà ïðîñòðàíñòâà En , â ëþáîé òî÷êå êîòîðîãî ñó-
ùåñòâóþò ïðîèçâîäíûå Fyj
 (x, y), j = 1, ..., n. Òîãäà äëÿ ìàêñèìèííîé ñòðà-
òåãèè x0   M0 = [a, b] âûïîëíåíî õîòÿ áû îäíî èç ñëåäóþùèõ äâóõ óñëîâèé:
1)   y1   N(x0 ) :
 Fx (x0 , y1 )(x0   a)(x0   b) =
= Fyj (x0 , y1 )(y 1
j   dj ) = 0, j = 1, ..., n. (5)
j   cj ))(y 1
2)   y1 = y2   N(x0 ) :
F (x0 , y1 ) = F (x0 , y 2 ), Fyj (x0 , y1 )(y 1
j   dj ) =
j   cj )(y1
= Fyj (x0 , y2 )(y 2
j   dj ) = 0, j = 1, ..., n. (6)
j   cj )(y2
Äîêàçàòåëüñòâî. Ïî òåîðåìå 3.7 äëÿ x0 âûïîëíåíî îäíî èç óñëîâèé
à),á) èëè â). Ïîêàæåì, ÷òî èç à) èëè â) ñëåäóåò óñëîâèå 1). Ïîñêîëüêó y 1  
N(x0 ), òî min
 F (x0 , y1 ||yj ) = F(x0 , y1 ). Òåïåðü îñòàåòñÿ âîñïîëüçîâàòüñÿ
cj  yj  d j
íåîáõîäèìûìè óñëîâèÿìè äëÿ òî÷êè ìèíèìóìà y1
j ôóíêöèè F (x0 , y1 ||yj ) íà
îòðåçêå [ci , dj ]. Èç íèõ ïîëó÷àåì óðàâíåíèÿ
 (x0 , y1 )(y1
j   dj ) = 0, j = 1, ..., n.
Fyj
j   cj ))(y1
Äàëåå, èç á) ñëåäóåò óñëîâèå 2).
Îòìåòèì îñîáåííîñòè ïîëó÷åííûõ íåîáõîäèìûõ óñëîâèé. Â ñèñòåìå (5)
÷èñëî óðàâíåíèé n + 1 ñîâïàäàåò ñ ÷èñëîì íåèçâåñòíûõ x0 , y1
n . Ïîýòî-
1 , ..., y1
ìó ìîæíî íàäåÿòüñÿ, ÷òî ñèñòåìà (5) èìååò êîíå÷íûé íàáîð ðåøåíèé. Â
ñèñòåìå (6) ÷èñëî óðàâíåíèé 2n + 1 òàêæå ñîâïàäàåò ñ ÷èñëîì íåèçâåñòíûõ
x0 , y 1
1 , ..., y1
n , y2
1 , ..., y2
n .
Ìîæíî ñëåäóþùèì îáðàçîì èñïîëüçîâàòü ýòè íåîáõîäèìûå óñëîâèÿ. Ñíà-
÷àëà íàõîäèì âñå ðåøåíèÿ ñèñòåì (5) è (6). Ïóñòü ïåðâûå êîìïîíåíòû x0
ýòèõ ðåøåíèé îáðàçóþò ìíîæåñòâî M  
0 , à ñîîòâåòñòâóþùèå êîìïîíåíòû
 min
 F (x, y).
y1 , y2 îáðàçóþò ìíîæåñòâî N  . Òîãäà x0   Arg max
x  M  
y  N  
0
Ïðèìåð. Ïóñòü F (x, y) =  (x   y + y3 )2 , M0 = N = [ 1, 1].Ïî ñìûñëó
F (x, y)   êâàäðàò îòêëîíåíèÿ (ñî çíàêîì ìèíóñ) âåëè÷èíû x îò çíà÷åíèÿ
30

ôóíêöèè  (x) = y   y 3 . Ãðàôèê ôóíêöèè  (x) èçîáðàæåí íà ðèñ. 1.
 (x)
T
v
E
 x
1 /
 3
v
1
 1
0
  1 /
 3
Ðèñ. 15.1

 

 

 

Çäåñü
 1/v3 , x < 0

 

 

 
 
 N(x) =
± 1/v3 , x = 0
  1/v3 , x > 0.
Ïðè y   N (x) Fx (x, y) =  2(x   y   y3 ) = 0. Ïîýòîìó äëÿ ìàêñèìèííîé
ñòðàòåãèè ñèñòåìà à) íå âûïîëíåíà, ñëåäîâàòåëüíî, âûïîëíåíà ñèñòåìà á).
v
Èìååì M  
0 = { 1, 0, 1}, N  = ± 1
3 ,

 

 

 

 

 

 

 

 

 1
v
v
3   1
3
 2
 2
 1   1 + 2
   1   2
v
v
 3
 3
 2
 2
.
0   2
   2
v
v
(F (x, y))M  
0  N   =
3
3
 2
 2
+1   1   2
   1 + 2
v
v
 3
 3
Îòñþäà x0 = 0   ìàêñèìèííàÿ ñòðàòåãèÿ. Îòìåòèì, ÷òî â ýòîì ïðèìåðå
âûïîëíåíî óñëîâèå 2), à óñëîâèå 1) äëÿ x0 íå âûïîëíåíî.
Ëåãêî ïîñòðîèòü ïðèìåð, ãäå, íàîáîðîò, äëÿ ìàêñèìèííîé ñòðàòåãèè x0
âûïîëíåíî óñëîâèå 1), à óñëîâèå 2) íå âûïîëíåíî. Ïóñòü, íàïðèìåð, ôóíêöèÿ
31

F (x, y) ñòðîãî âûïóêëà ïî y. Â ýòîì ñëó÷àå ïðè ëþáîì x   M0 ìíîæåñòâî
N(x) ñîñòîèò èç åäèíñòâåííîãî ýëåìåíòà.
§15. Çàäà÷è îïòèìàëüíîãî ðàñïðåäåëåíèÿ ðåñóðñîâ.
Â ýòîì ïàðàãðàôå ìû ðàññìîòðèì íåêîòîðûå çàäà÷è îïòèìàëüíîãî ðàñ-
ïðåäåëåíèÿ ðåñóðñîâ. Áóäóò ñôîðìóëèðîâàíû óñëîâèÿ îïòèìàëüíîñòè, à
òàêæå óêàçàíû àëãîðèòìû ïîèñêà îïòèìàëüíûõ ðàñïðåäåëåíèé ðåñóðñîâ.
Ïóñòü i = 1, ..., n,   íîìåðà n ïóíêòîâ, ïî êîòîðûì îïåðèðóþùàÿ ñòîðîíà
ðàñïðåäåëÿåò ðåñóðñ. ×åðåç fi (t) îáîçíà÷èì ôóíêöèþ, îïðåäåëÿþùóþ ýô-
ôåêò îò âëîæåíèÿ ðåñóðñà â êîëè÷åñòâå t â i-é ïóíêò. Âåêòîð x = (x1 , ..., xn )
çàäàåò ñòðàòåãèþ ðàñïðåäåëåíèÿ ðåcóðñà. Ïðè ýòîì íà i-é ïóíêò íàïðàâëÿ-
åòñÿ ðåñóðñ â êîëè÷åñòâå xi .
Áóäåì ðàññìàòðèâàòü äâà âèäà çàäà÷: íåïðåðûâíûå, ãäå ðåñóðñ ïðåäïî-
ëàãàåòñÿ áåñêîíå÷íî-äåëèìûì, è äèñêðåòíûå, ãäå ðåñóðñ   øòó÷íûé, à A
è xi   öåëûå ÷èñëà. Äëÿ íåïðåðûâíîé çàäà÷è ìíîæåñòâî ñòðàòåãèé èìååò
âèä
 n
 M0 = {x   En |
 xi = A, xi   0, i = 1, ..., n},
i =1
à äëÿ äèñêðåòíîé  
 n
M0 = {x   En |
 xi = A, xi   0, xi   Z, i = 1, ..., n},
i =1
ãäå Z   ìíîæåñòâî öåëûõ ÷èñåë.
Ðàññìîòðèì ñëåäóþùóþ íåïðåðûâíóþ çàäà÷ó:
max
 min
 fi (xi ) = min
 fi (x0
i ). (I )
1  i  n
1  i  n
x  M0
Ïî ñìûñëó îïåðèðóþùàÿ ñòîðîíà ñòðåìèòñÿ ìàêñèìèçèðîâàòü ñâåðòêó âè-
äà min
 fi (xi ), ò.å. ìèíèìàëüíûé ýôôåêò îò âëîæåíèÿ ðåñóðñà. Ýòî îòâå÷à-
1  i  n
åò ñîöèàëèñòè÷åñêîìó ïðèíöèïó: "÷òîáû íå áûëî áåäíûõ". Ìàêñèìèííóþ
ñòðàòåãèþ x0 áóäåì íàçûâàòü îïòèìàëüíûì ðàñïðåäåëåíèåì ðåñóðñà.
Çàäà÷ó (I) áóäåì ðàññìàòðèâàòü â ïðåäïîëîæåíèè, ÷òî âñå ôóíêöèè fi (t)
íåïðåðûâíû è âîçðàñòàþò íà îòðåçêå [0, A]. Êðîìå òîãî, áåç ïîòåðè îáùíî-
ñòè áóäåì ñ÷èòàòü, ÷òî
 f1 (0)   f2 (0)   ...   fn (0).
Áóäåì óñëîâíî ãîâîðèòü, ÷òî ïåðâûé ïóíêò ÿâëÿåòñÿ ñëàáåéøèì: åñëè ïóíê-
òàì íå âûäåëÿåòñÿ ðåñóðñ, òî ýôôåêò íà ïåðâîì ïóíêòå áóäåò íàèìåíüøèì.
Òåîðåìà 3.8. (ïðèíöèï óðàâíèâàíèÿ Þ.Á. Ãåðìåéåðà). Â ñäåëàííûõ
ïðåäïîëîæåíèÿõ ïóñòü x0   îïòèìàëüíîå ðàñïðåäåëåíèå ðåñóðñà â çàäà÷å
(I). Òîãäà äëÿ x0 âûïîëíåíî ñëåäóþùåå íåîáõîäèìîå è äîñòàòî÷íîå óñëîâèå:
32

íàéäåòñÿ òàêîå öåëîå k, 1   k   n, ÷òî
fi (x0
k ) < fk+1 (0), i = 1, ..., k   1,
i ) = fk(x0
 (1)
x0
i = 0, i = k + 1, ..., n.
Åñëè f1 (0) = f2 (0) = ... = fn (0), òî k = n. Âî âñåõ ñëó÷àÿõ îïòèìàëüíîå
ðàñïðåäåëåíèå ðåñóðñà x0 åäèíñòâåííî.
Çàìå÷àíèå. Îïòèìàëüíîå ðàñïðåäåëåíèå ðåñóðñà ïðåäïîëàãàåò åãî âû-
äåëåíèå íåñêîëüêèì ñëàáûì ïóíêòàì ñ âûðàâíèâàíèåì ýôôåêòà ïî ýòèì
ïóíêòàì.
Äîêàçàòåëüñòâî. Íåîáõîäèìîñòü. Çàìåòèì, ÷òî îïòèìàëüíîå ðàñïðåäå-
ëåíèå x0 ñóùåñòâóåò, ïîñêîëüêó ôóíêöèÿ min
 fi (xi ) íåïðåðûâíà íà êîì-
1  i  n
ïàêòå M0 . Îïðåäåëèì ÷èñëî k èç óñëîâèÿ
fk (0)   min
 fi (x0
i ) < fk +1 (0). (2)
1  i  n
Åñëè k = n, òî âòîðîå íåðàâåíñòâî â (2) îòñóòñòâóåò. Íåòðóäíî âèäåòü, ÷òî
óêàçàííîå k âñåãäà íàéäåòñÿ. Äåéñòâèòåëüíî, â ñèëó ìîíîòîííîñòè ôóíêöèé
fi (t) ñïðàâåäëèâî íåðàâåíñòâî
f1 (0)   min
 fi (x0
i ).
1  i  n
Ïîýòîìó ÷èñëî min
 fi (x0
i ) ïðèíàäëåæèò îäíîìó èç ïîëóèíòåðâàëîâ
1  i  n
[fi (0), fi +1 (0)), i = 1, ..., n.
Çäåñü ïðè fi (0) = fi+ 1 (0) ñîîòâåòñòâóþùèé èíòåðâàë ïóñò, à fn + 1 (0) ïîëà-
ãàåòñÿ ðàâíûì  .
Ïóñòü k < n. Ïîêàæåì, ÷òî x0
i = 0, i = k + 1, ..., n. Ïðåäïîëîæèì, ÷òî
 > 0. Îïðåäåëèì ñëåäóþùèé âåêòîð z :
ïðè íåêîòîðîì i1   k + 1 x0
i 1
 x0
i 1    , i = i1 ,
zi =
x0
i 1 +  
n   1 , i = i1 ,   > 0.
Ïðè ìàëîì   > 0 âåêòîð z ïðèíàäëåæèò M0 . Äåéñòâèòåëüíî, åãî êîìïî-
 ) ïîëîæèòåëüíû, à èõ ñóììà ðàâíà A.
íåíòû ïðè     (0, x0
i 1
Èñïîëüçóÿ ìîíîòîííîñòü ôóíêöèé fi (t), ïîëó÷èì, ÷òî ïðè i = i1
fi (zi ) > fi (x0
 fi (x0
i )   min
i ),
1  i  n
à ïðè i = i1
> min
 fi (x0
i ).
 fi 1 (zi 1 ) > fi 1 (0)   fk +1 (0)(2 )
1  i  n
Îòñþäà min
 fi (z) > min
 fi (x0
i ), ÷òî ïðîòèâîðå÷èò îïòèìàëüíîñòè x0 .
1  i  n
1  i  n
33

Äîêàæåì, ÷òî fi (x0
 fi (x0
i ) = min
i ) ïðè i = 1, ..., k. Ïðåäïîëîæèì ïðî-
1  i  n
òèâíîå. Òîãäà íàéäåòñÿ òàêîé íîìåð i1   k, ÷òî fi 1 (x0
 fi (x0
i 1 ) > min
i ). Ïîêà-
1  i   n
 > 0. Äåéñòâèòåëüíî, â ïðîòèâíîì ñëó÷àå min
æåì, ÷òî x0
 fi (x0
i ) < fi 1 (0)  
i 1
1  i  n
fk (0), ÷òî ïðîòèâîðå÷èò (2).
Èòàê, x0
i 1 > 0. Âîçüìåì îïðåäåëåííîå âûøå ðàñïðåäåëåíèå z. Êàê è ðàíü-
øå, ïðè i = i1 âûïîëíåíî íåðàâåíñòâî fi (zi ) > min
 fi (x0
i ), à íåðàâåíñòâî
1  i  n
    ) > min
fi1 (zi 1 ) = fi 1 (x0
 fi (x0
i ) áóäåò âûïîëíåíî ïðè ìàëîì   > 0,
i 1
1  i  n
ïîñêîëüêó ôóíêöèè fi (t) íåïðåðûâíû. Îòñþäà, êàê è âûøå, ïîëó÷àåì ïðî-
òèâîðå÷èå. Óñëîâèå (1) äîêàçàíî.
Äîñòàòî÷íîñòü. Ïóñòü ñòðàòåãèÿ x0   M0 óäîâëåòâîðÿåò óñëîâèþ (1).
Ïîêàæåì, ÷òî x0   îïòèìàëüíîå ðàñïðåäåëåíèå ðåñóðñà. Âîçüìåì ïðîèç-
âîëüíóþ ñòðàòåãèþ x   M0 , îòëè÷íóþ îò x0 . Ïîñêîëüêó ñóììû êîìïîíåíò
ýòèõ âåêòîðîâ ðàâíû A, ñóùåñòâóåò òàêîé íîìåð j, ÷òî xj < x0
j . Îòñþäà ñëå-
äóåò, ÷òî x0
 fi (xi )   fj (xj ) < fj (x0
 fi (x0
j > 0. Ïîýòîìó min
j ) = min
i ), ò.å.
1  i  n
1  i  n
x0   îïòèìàëüíîå ðàñïðåäåëåíèå ðåñóðñà. Åäèíñòâåííîñòü îïòèìàëüíîãî
ðàñïðåäåëåíèÿ x0 ñëåäóåò èç ïîñëåäíåãî ñòðîãîãî íåðàâåíñòâà.
Ðàññìîòðèì àëãîðèòì ïîèñêà îïòèìàëüíîãî ðàñïðåäåëåíèÿ ðåñóðñà. Áå-
ðåì ïîñëåäîâàòåëüíî k = n, n   1, ..., 1 è ðåøàåì ñèñòåìó óðàâíåíèé
 n
fi (x0
 x0
i = 0, i = k + 1, ..., n,
i = A (3)
i ) = C, i = 1, ..., k, x0
i= 1
îòíîñèòåëüíî íåèçâåñòíûõ C, x0
n . Åñëè ïîëó÷åííîå ðåøåíèå èìååò íåîò-
1 , ..., x0
ðèöàòåëüíûå êîìïîíåíòû x0
i è ïðè k < n âûïîëíåíî íåðàâåíñòâî C <
fk+1 (0), òî x0   îïòèìàëüíîå ðàñïðåäåëåíèå ðåñóðñà. Â ïðîòèâíîì ñëó÷àå
óìåíüøàåì çíà÷åíèå k è âíîâü ðåøàåì ñèñòåìó.
×àñòî âñòðå÷àåòñÿ îïòèìèçàöèîííàÿ çàäà÷à âèäà
min
 max
 fi (xi ) = max
 fi (x0
i ).
1  i  n
1  i  n
x  M0
Çäåñü ïðåäïîëàãàåòñÿ, ÷òî êàæäàÿ ôóíêöèÿ fi (t) óáûâàåò, åå çíà÷åíèå ìîæ-
íî èíòåðïðåòèðîâàòü êàê âåëè÷èíó óùåðáà ïðè âëîæåíèè ðåñóðñà â êîëè-
÷åñòâå t.
Ïðèìåð. Îïòèìèçàöèÿ ñòðóêòóðû ñòðàõîâîãî ïîðòôåëÿ. Ñòðàõîâàÿ êîì-
ïàíèÿ ïðîâîäèò ìàññîâîå ñòðàõîâàíèå ïî íåñêîëüêèì âèäàì ðèñêîâ. Ïóñòü
xi   ÷èñëî äîãîâîðîâ, çàêëþ÷åííûõ ïî i-ó âèäó ñòðàõîâàíèÿ, à  i j   ñëó-
÷àéíàÿ âåëè÷èíà èñêà ïî j-ó äîãîâîðó, j = 1, ..., xi . Áóäåì ñ÷èòàòü, ÷òî
ñëó÷àéíûå âåëè÷èíû  i j íåçàâèñèìû, êàæäàÿ èç íèõ èìååò ìàòåìàòè÷åñêîå
îæèäàíèå mi è äèñïåðñèþ Vi . Âåëè÷èíà mi   ýòî ñòîèìîñòü ïîëèñà áåç
íàäáàâîê çà ðèñê è òåêóùèõ ðàñõîäîâ êîìïàíèè. Ïóñòü  i   îòíîñèòåëüíàÿ
ðèñêîâàÿ íàäáàâêà, êîòîðàÿ âçèìàåòñÿ ñ öåëüþ îáåçîïàñèòü ñòðàõîâóþ êîì-
ïàíèþ îò ðàçîðåíèÿ. Ñòîèìîñòü ïîëèñà ïðè ýòîì âîçðàñòàåò äî âåëè÷èíû
  i j   ñóììàðíûé èñê ñî ñòîðîíû êëèåíòîâ ïî i-ó
mi (1 +  i ). Ïóñòü  i = x i
j =1
34

âèäó ñòðàõîâàíèÿ. Íàäáàâêà  i âûáèðàåòñÿ èç óñëîâèÿ, ñîñòîÿùåãî â òîì,
÷òî ñîáûòèå1
 de f
=  i   xi mi
{ i   xi mi (1 +  i )} = Yi
vxi Vi
   xi mi  i
vxi Vi
äîëæíî âûïîëíÿòüñÿ ñ ìàëîé âåðîÿòíîñòüþ  . Ïðè áîëüøèõ xi ñëó÷àéíàÿ
âåëè÷èíà Yi èìååò ñòàíäàðòíîå íîðìàëüíîå ðàñïðåäåëåíèå ñ íóëåâûì ìà-
òåìàòè÷åñêèì îæèäàíèåì è åäèíè÷íîé äèñïåðñèåé. Óêàçàííîå ñîáûòèå âû-
ïîëíåíî ñ òðåáóåìîé âåðîÿòíîñòüþ  , åñëè ïðàâàÿ ÷àñòü íåðàâåíñòâà ðàâíà
êâàíòèëþ y  ôóíêöèè ðàñïðåäåëåíèÿ íîðìàëüíîãî çàêîíà
 y
2 dx,
 (y) = 1
v2 
 e  x 2
   
ò.å. y  íàõîäèòñÿ èç óðàâíåíèÿ 1    (y  ) =  . Îòñþäà ïîëó÷àåì ôîðìóëû
äëÿ îòíîñèòåëüíûõ ðèñêîâûõ íàäáàâîê ïî êàæäîìó âèäó ñòðàõîâàíèÿ
 vVi y 
 , i = 1, ..., n.
 i (xi ) =
vxi mi
Ïóñòü A   îáùåå ÷èñëî äîãîâîðîâ. Âåêòîð x   M0 îòðàæàåò ñòðóêòóðó
ñòðàõîâîãî ïîðòôåëÿ. Çäåñü äîïóñêàåòñÿ íåöåëîå ÷èñëî äîãîâîðîâ xi . Ðàñ-
ñìîòðèì çàäà÷ó min
 max
  i (xi ). ×åì ìåíüøå íàèáîëüøàÿ îòíîñèòåëüíàÿ
1  i  n
x  M 0
ðèñêîâàÿ íàäáàâêà, òåì áîëåå êîíêóðåíòíî-ñïîñîáíà ñòðàõîâàÿ êîìïàíèÿ.
Ïåðåéäåì òåïåðü ê çàäà÷å äèñêðåòíîãî ìàêñèìèíà:
max
 min
 fi (xi ) = min
 fi (x 
i ). (I)
1  i  n
1  i  n
x  M0
Çäåñü fi (t)   âîçðàñòàþùèå ôóíêöèè öåëîãî àðãóìåíòà.
Ïîëîæèì I = {1, ..., n} è äëÿ x   M0 îïðåäåëèì ìíîæåñòâî
I (x) = Arg min
 fi (x).
i   I
Îáîçíà÷èì ÷åðåç |I(x)| ÷èñëî ýëåìåíòîâ ìíîæåñòâà I(x).
Òåîðåìà 3.9. Ïóñòü x    òàêîå îïòèìàëüíîå ðàñïðåäåëåíèå ðåñóðñîâ
çàäà÷è (I) , ïðè êîòîðîì âåëè÷èíà |I (x  )| ìèíèìàëüíà ñðåäè âñåõ îïòèìàëü-
íûõ ðàñïðåäåëåíèé. Òîãäà íåîáõîäèìî âûïîëíåíî óñëîâèå:
åñëè x 
 fi (x 
j > 0, òî min
j   1). (3)
i )   fj (x 
1  i  n
Óñëîâèå (3) ÿâëÿåòñÿ äîñòàòî÷íûì óñëîâèåì îïòèìàëüíîñòè.
1 Åãî íàçûâàþò òåõíè÷åñêèì ðàçîðåíèåì ïî i-ó âèäó ñòðàõîâàíèÿ.
35

Çàìå÷àíèå. Óñëîâèå (3) ïîêàçûâàåò, ÷òî ïðè ïîëîæèòåëüíîé êîìïîíåíòå
x 
 fi (x 
j ) áëèçêà ê min
i ). Ýòî äèñêðåòíûé àíàëîã ïðèíöèïà
j âåëè÷èíà fj (x 
1  i  n
óðàâíèâàíèÿ.
Äîêàçàòåëüñòâî. Íåîáõîäèìîñòü. Ïóñòü x    óêàçàííîå â óñëîâèè òåî-
ðåìû îïòèìàëüíîå ðàñïðåäåëåíèå ðåñóðñà çàäà÷è (I) . Ïðåäïîëîæèì, ÷òî
óñëîâèå (3) íå âûïîëíåíî. Òîãäà íàéäåòñÿ òàêîé íîìåð j, ÷òî x 
j > 0 è
  I(x  ). Âîçüìåì íîìåð
fj (x 
 fi (x 
j   1) > min
i ). Îòñþäà ñëåäóåò, ÷òî j /
1  i  n
l   I(x ) è îïðåäåëèì íîâîå ðàñïðåäåëåíèå z   M0 :

 
x 
j   1, i = j,

zi =
x 
l + 1, i = l,
x 
i , i = j, l.
 fi (zi ) >
Òîãäà fl (zl ) > fl (x 
 fi (x 
l ), fj (zj ) > min
i ). Îòñþäà ñëåäóåò, ÷òî min
1  i  n
1  i  n
min
 fi (zi ) = min
 fi (x 
 fi (x 
i )   min
i ), òàê êàê x    îïòèìàëüíîå ðàñ-
1  i  n
1  i  n
1   i  n
ïðåäåëåíèå ðåñóðñà. Èòàê, ðàñïðåäåëåíèå z òàêæå îïòèìàëüíî. Ïðè ýòîì
I(z) = I(x )\{l}, ÷òî ïðîòèâîðå÷èò îïðåäåëåíèþ x  .
Äîñòàòî÷íîñòü. Ïóñòü óñëîâèå (3) âûïîëíåíî. Âîçüìåì ïðîèçâîëüíîå x  
M0 , x = x . Òîãäà íàéäåòñÿ òàêîé íîìåð j, ÷òî x 
j > 0 è
j > xj . Îòñþäà x 
min
 fi (xi ).
 fi (x 
  fj (x 
j   1)   fj (xj )   min
i )(3 )
1  i  n
1  i  n
Èòàê, x    îïòèìàëüíîå ðàñïðåäåëåíèå ðåñóðñà.
Ðàññìîòðèì àëãîðèòì ïîèñêà îïòèìàëüíîãî ðàñïðåäåëåíèÿ çàäà÷è (I) .
Ïóñòü x(1 )   ïðîèçâîëüíîå ðàñïðåäåëåíèå ðåñóðñà. Äîïóñòèì, ÷òî àëãîðèòì
ïðîðàáîòàë äî k-ãî øàãà è ìû ïîëó÷èëè ðàñïðåäåëåíèå x(k) . Åñëè äëÿ x(k )
âûïîëíåíî óñëîâèå (3), òî ïî òåîðåìå 3.9 îíî è áóäåò èñêîìûì îïòèìàëüíûì
ðàñïðåäåëåíèåì. Äîïóñòèì, ÷òî äëÿ x(k ) óñëîâèå (3) íå âûïîëíåíî. Òîãäà
íàéäåòñÿ òàêîé íîìåð j, ÷òî x( k)
 fi (x 
j   1) > min
i ). Îïðåäåëèì
j > 0 è fj (x 
1  i  n
íîâîå ðàñïðåäåëåíèå x(k +1 ) = z, êàê ýòî ñäåëàíî â äîêàçàòåëüñòâå òåîðåìû
3.9. Ïðè ýòîì íóæíî çàìåíèòü x  íà x(k) . Ìîãóò âîçíèêíóòü äâà ñëó÷àÿ:
1) I(x(k) ) = {l}. Òîãäà
min
 fi (x(k+1 )
i ) > min
 fi (x(k)
i ).
1  i  n
1  i  n
2) |I(x(k ) )| > 1. Òîãäà
min
 fi (x(k +1 )
i ) = min
 fi (x(k )
i ), íî |I(x(k +1 ) )| < |I(x(k) )|.
1  i  n
1  i  n
Òàêèì îáðàçîì, íà êàæäîì øàãå àëãîðèòìà ëèáî óâåëè÷èâàåòñÿ çíà÷å-
íèå ôóíêöèè ìèíèìóìà, ëèáî ñîêðàùàåòñÿ ìíîæåñòâî I(x(k) ). Îòñþäà ñëå-
äóåò, ÷òî àëãîðèòì çàêîí÷èò ðàáîòó ÷åðåç êîíå÷íîå ÷èñëî øàãîâ, ïîñêîëüêó
ìíîæåñòâî M0 ñîäåðæèò êîíå÷íîå ÷èñëî ýëåìåíòîâ.
36

Íà ïðàêòèêå â êà÷åñòâå íà÷àëüíîãî áåðóò ðàñïðåäåëåíèå x(1 ) , áëèçêîå ê
îïòèìàëüíîìó ðàñïðåäåëåíèþ ñîîòâåòñòâóþùåé íåïðåðûâíîé çàäà÷è.
Ïðèìåð. Ðàññìîòðèì çàäà÷ó íàõîæäåíèÿ max
 min
 ix2
i , ãäå
1  i  4
x  M0
 4
M0 = {x   E4 |
 xi = 10, xi   0, xi   Z, i = 1, 2, 3, 4}.
i= 1
Äëÿ ðåøåíèÿ ïðèìåíèì óêàçàííûé àëãîðèòì. Âîçüìåì íà÷àëüíîå ðàñïðå-
äåëåíèå x(1 ) = (4, 3, 2, 1). Âñå âû÷èñëåíèÿ ñâåäåì â òàáëèöó
 2 i x(1 )
 2 i x( 2 )
i x(1 )
i   1 2
i i x(1 )
i
i   1 2 x(2 )
i i x(2 )
i
1 4 16 9 3 9 4
2 3 18 8 3 18 8
3 2 12 3 2 12 3
4 1 4 0 2 16 4
Çäåñü I(x(1 )) = {4} è óñëîâèå (3) äëÿ x(1 ) ) íå âûïîëíåíî ïðè j = 1. Äàëåå,
I(x( 2 )) = {1} è óñëîâèå (3) âûïîëíåíî. Èòàê, x(2 )   îïòèìàëüíîå ðàñïðåäå-
ëåíèå ðåñóðñà.
Óïðàæíåíèå. Íàéäèòå îïòèìàëüíîå ðàñïðåäåëåíèå ðåñóðñà â ñîîòâåò-
ñòâóþùåé íåïðåðûâíîé çàäà÷å.
Ðàññìîòðèì åùå îäíó íåïðåðûâíóþ çàäà÷ó:
 n
 n
max
 fi (xi ) =
 fi (x0
i ). (II )
x M 0
i =1
i=1
Ïðèìåð èíòåðïðåòàöèè çàäà÷è. Èíâåñòîð ðàñïðåäåëÿåò êàïèòàë A ïî n ïðî-
åêòàì, ãäå fi (t)   ïðèáûëü, ïîëó÷àåìàÿ îò âëîæåíèÿ êàïèòàëà t â i-é ïðîåêò.
Â îòëè÷èå îò çàäà÷è (I), ôóíêöèè fi (t) íåîáÿçàòåëüíî âîçðàñòàþùèå. Ïðåä-
ïîëîæèì, ÷òî îíè äèôôåðåíöèðóåìû íà îòðåçêå [0, A].
Òåîðåìà 3.10.(Ëåììà Ãèááñà). Ïóñòü x0   îïòèìàëüíîå ðàñïðåäåëåíèå
ðåñóðñà â çàäà÷å (II). Òîãäà íàéäåòñÿ òàêîå ÷èñëî  , ÷òî âûïîëíåíî ñëåäó-
þùåå íåîáõîäèìîå óñëîâèå:
 fi (x0
i > 0,
i ) =  , x0
 (1)
fi (x0
i = 0.
i )    , x0
Åñëè ôóíêöèè fi (t) âîãíóòû, òî (1) ÿâëÿåòñÿ äîñòàòî÷íûì óñëîâèåì
îïòèìàëüíîñòè. Åñëè äîïîëíèòåëüíî èçâåñòíî, ÷òî ôóíêöèè fi (t) äâàæäû
äèôôåðåíöèðóåìû è
f1 (0)   f2 (0)   ...   fn (0), fi (0) < 0, i = 1, ..., n,
òî íàéäåòñÿ òàêîé íîìåð l, ÷òî
x0
i = 0, i = l + 1, ..., n.
i > 0, i = 1, ..., l , x0
37

Çàìå÷àíèå. Óñëîâèå (1) ÿâëÿåòñÿ ïðèíöèïîì óðàâíèâàíèÿ äëÿ ïðîèçâîä-
íûõ fi (t). Ïîñëåäíåå óòâåðæäåíèå îçíà÷àåò, ÷òî ïðè óïîðÿäî÷åííîñòè ïðî-
èçâîäíûõ fi (0) ïî óáûâàíèþ âëîæåíèå ðåñóðñà â ïåðâûå ïóíêòû íàèáîëåå
ýôôåêòèâíî.
Äîêàçàòåëüñòâî. Íåîáõîäèìîñòü. Ïóñòü x0   îïòèìàëüíîå ðàñïðåäåëå-
íèå ðåñóðñîâ â çàäà÷å (II ), à x0
i > 0. Âîçüìåì ïðîèçâîëüíûé íîìåð j = i è
îïðåäåëèì ôóíêöèþ îò  
 fk (x0 ).
 ( ) = fi (x0
j +  ) +
i    ) + fj (x0
 k=i ,j
íà îòðåçêå [0, x0
i ]. Ïîñêîëüêó x0   îïòèìàëüíîå ðàñïðåäåëåíèå ðåñóðñà,  ( )
äîñòèãàåò íà îòðåçêå [0, x0
i ] íàèáîëüøåãî çíà÷åíèÿ â òî÷êå   = 0. Ïîýòîìó
  (0)   0 èëè
 (2)
 fj (x0
i ).
j )   fi (x0
Åñëè x0
j > 0, òî, ìåíÿÿ ìåñòàìè i è j, ïîëó÷èì íåðàâåíñòâî
 (3)
fj (x0
i ).
j )   fi (x0
Èç (2) è (3) ñëåäóåò, ÷òî fj (x0
i ) =  , ò.å. ïðè ïîëîæèòåëüíûõ âëî-
j ) = fi (x0
æåíèÿõ ðåñóðñà â ïóíêòû i è j çíà÷åíèÿ ñîîòâåòñòâóþùèõ ïðîèçâîäíûõ
ñîâïàäàþò. Èç (2) ñëåäóåò, ÷òî fj (x0
j )     ïðè âñåõ j. Óñëîâèå (1) äîêàçàíî.
Äîñòàòî÷íîñòü. Ïóñòü ôóíêöèè fi (t) âîãíóòû è ðàñïðåäåëåíèå ðåñóðñà x0
óäîâëåòâîðÿåò óñëîâèþ (1). Âîçüìåì ïðîèçâîëüíîå ðàñïðåäåëåíèå x   M0 .
Èç âîãíóòîñòè ôóíêöèé fi (t) èìååì íåðàâåíñòâî:
n
 n
 (fi (xi )   fi (x0
 fi (x0
i ))  
i ).
i )(xi   x0
i =1
i =1
Åñëè x0
i = 0,
i > 0, òî ïîäñòàâèì â ïîñëåäíåå âûðàæåíèå fi (x0
i ) =  , à åñëè x0
òî xi   x0
i ) îöåíèâàåì ñâåðõó âåëè÷èíîé  . Â
i = xi   0 è ïðîèçâîäíóþ fi (x0
ðåçóëüòàòå
 n
 n
 fi (x0
  (xi   x0
i )  
i ) =  (A   A) = 0.
i )(xi   x0
i =1
i =1
Èòàê, n
 fi (xi )   n
 fi (x0
i )) ïðè ëþáîì x   M0 , ÷òî è äîêàçûâàåò îïòèìàëü-
i =1
i= 1
íîñòü x0 .
Ïðåäïîëîæèì, ÷òî
f1 (0)   f2 (0)   ...   fn (0), fi (0) < 0, i = 1, ..., n.
Ïðåäïîëîæèì, ÷òî íàéäåòñÿ òàêîé íîìåð i, ÷òî x0
i +1 > 0. Òîãäà
i = 0, x0
fi (x0
    = fi +1 (x0
i +1 ) < fi +1 (0).
i ) = fi (0)(1 )
38

Ïîñëåäíåå íåðàâåíñòâî ñëåäóåò èç óñëîâèÿ fi +1 (0) < 0. Ïîýòîìó fi (0) <
fi+ 1 (0) (ïðîòèâîðå÷èå).
Ïðèìåð. Çàäà÷à ïîèñêà îáúåêòà.
Îáúåêò ïðÿ÷åòñÿ â n âîçìîæíûõ îáëàñòÿõ ñ íîìåðàìè i = 1, ..., n. Åñ-
ëè îí íàõîäèòñÿ â i-îé îáëàñòè è ïîèñê â íåé âåäåòñÿ â òå÷åíèå âðåìåíè
t, òî óñëîâíàÿ âåðîÿòíîñòü åãî îáíàðóæåíèÿ ðàâíà 1   e µ i t , ãäå µi > 0.
Îáîçíà÷èì ÷åðåç pi èçâåñòíóþ àïðèîðíóþ âåðîÿòíîñòü íàõîæäåíèÿ îáúåê-
òà â i-é îáëàñòè. Ïóñòü A   îáùåå âðåìÿ ïîèñêà îáúåêòà. Ñòðàòåãèÿ ïîèñêà
x = (x1 , ..., xn )   M0 îçíà÷àåò, ÷òî îáúåêò â îáëàñòè i èùåòñÿ â òå÷åíèå âðå-
ìåíè xi . Òîãäà n
 pi (1  e µ i x i )   ïîëíàÿ âåðîÿòíîñòü îáíàðóæåíèÿ îáúåêòà,
i =1
êîòîðóþ íåîáõîäèìî ìèíèìèçèðîâàòü.
Îïðåäåëèì ôóíêöèè fi (t) = pi (1   e  µi t) è ðåøèì çàäà÷ó (II) . Çàìåòèì,
÷òî fi (t) =  pi µ2
i (1   e  µi t) < 0. Ñëåäîâàòåëüíî, ôóíêöèè fi (t) ÿâëÿþòñÿ
âîãíóòûìè. Óïîðÿäî÷èì çíà÷åíèÿ ïðîèçâîäíûõ â íóëå fi (0) = pi µi :
p1 µ1   p2 µ2   ...   pn µn .
Â ñîîòâåòñòâèè ñ ëåììîé Ãèááñà íàéäåòñÿ òàêîé íîìåð l, ÷òî
x0
i = 0, i = l + 1, ..., n.
i > 0, i = 1, ..., l , x0
Çàïèøåì óñëîâèå (1)
 fi (x0
i ) =  , i = 1, ..., l,
 (1)
fi (x0
i )    , i = l + 1, ..., n.
Ïîëó÷àåì ñèñòåìó óðàâíåíèé Îòñþäà íàõîäèì
   1
 ln  , i = 1, ..., l. (2)
x0
i = ln(pi µi )
µi
µi
Ñêëàäûâàÿ ýòè ðàâåíñòâà, ïîëó÷èì
 l
 l
 1
 ln(pk µk )
A =
   ln  
 .
µk
µk
k =1
k =1
Îòñþäà íàéäåì ln   è ïîñëå ïîäñòàíîâêè â (2) íàõîäèì
  1
 l
 l
 1
 ln(pk µk )
   1
   A
 , i = 1, ..., l .
x0
i = ln(pi µi )
µi
µi
µk
µk
k=1
k =1
Ïîñêîëüêó ïðîèçâåäåíèÿ pi µi óïîðÿäî÷åíû, äëÿ òîãî ÷òîáû êîìïîíåíòû
x0
i , i = 1, ..., l, áûëè ïîëîæèòåëüíûìè, äîñòàòî÷íî ïîòðåáîâàòü âûïîëíåíèÿ
íåðàâåíñòâà x0
l > 0 èëè
 l
 l
 1
 ln(pk µk )
A >
 . (4)
   ln(pl µl )
µk
µk
k=1
k =1
39

Íåîáõîäèìî òàêæå ïðîâåðèòü íåðàâåíñòâà
fi (0) = pi µi    , i = l + 1, ..., n,
èëè pl +1 µl+1    , ïîñêîëüêó pi µi óïîðÿäî÷åíû. Ïîñëåäíåå íåðàâåíñòâî ïðî-
ëîãàðèôìèðóåì è ïîäñòàâèì âûðàæåíèå äëÿ
  1
 l
 l
 1
 ln(pk µk )
ln   =
   A
 .
µk
µk
k =1
k=1
Â ðåçóëüòàòå ïîëó÷èì
 l
 l
 1
 ln(pk µk )
  
   A.
ln(pl +1 µl +1 )
µk
µk
k=1
k=1
Äîáàâèì ê îáåèì ÷àñòÿì âûðàæåíèå ln(pl +1 µl +1 )(µl +1 ) 1 è â ðåçóëüòàòå
ïîëó÷èì íåðàâåíñòâî
 l+1
 l +1
 1
 ln(pk µk )
A  
 . (5)
   ln(pl +1 µl+1 )
µk
µk
k=1
k =1
Èòàê, íîìåð l âûáèðàåòñÿ èç óñëîâèé (4),(5), ëèáî l = n. Çàìåòèì, ÷òî
íåðàâåíñòâî (4) âûïîëíåíî ïðè l = 1. Íåòðóäíî âèäåòü, ÷òî âûðàæåíèå
l
 l
 1
 ln(pk µk )
   ln(pl µl )
µk
µk
k=1
k =1
íå óáûâàåò ïî l. Èññëåäîâàíèå ìîäåëè ïîëíîñòüþ çàâåðøåíî.
Ðàññìîòðèì äèñêðåòíûé àíàëîã çàäà÷è (II) :
 n
 n
max
 fi (xi ) =
 fi (x 
i ) (II) .
x  M0
i= 1
i =1
Çäåñü fi (t)   âîçðàñòàþùèå ôóíêöèè öåëîãî àðãóìåíòà. Ïóñòü, êðîìå òîãî,
âûïîëíåíî ñëåäóþùåå óñëîâèå âîãíóòîñòè:
åñëè xi > 0, òî fi (xi )   0.5(fi (xi + 1)   fi (xi   1)) èëè
fi (xi )   fi (xi   1)   fi (xi + 1)   fi (xi ). (1)
Íåðàâåíñòâî (1) îçíà÷àåò, ÷òî ðàçíîñòü ìåæäó çíà÷åíèÿìè ôóíêöèè fi â
ñîñåäíèõ òî÷êàõ íå âîçðàñòàåò.
Òåîðåìà 3.10. (Êðèòåðèé Ãðîññà). Â ñäåëàííûõ ïðåäïîëîæåíèÿõ ïóñòü
x    îïòèìàëüíîå ðàñïðåäåëåíèå ðåñóðñà â çàäà÷å (II) . Òîãäà äëÿ x  âû-
ïîëíåíî íåîáõîäèìîå è äîñòàòî÷íîå óñëîâèå:
x 
 [fi (x 
j   1)   max
i )]. (2)
j > 0   fj (x 
j )   fj (x 
i + 1)   fi (x 
i  i  n
40

Çàìå÷àíèå. Ïðè ïîëîæèòåëüíîì x 
j   1), ïðåä-
j ðàçíîñòü fj (x 
j )   fj (x 
ñòàâëÿþùàÿ ñîáîé äèñêðåòíóþ ïðîèçâîäíóþ, áëèçêà ê ïðàâîé ÷àñòè íåðà-
âåíñòâà (2). Òàêèì îáðàçîì, óñëîâèå (2) ïðåäñòàâëÿåò ñîáîé äèñêðåòíûé
àíàëîã ïðèíöèïà óðàâíèâàíèÿ äëÿ ïðîèçâîäíûõ.
Äîêàçàòåëüñòâî. Íåîáõîäèìîñòü. Ïóñòü x    îïòèìàëüíîå ðàñïðåäåëåíèå
ðåñóðñà â çàäà÷å (II ) . Ïîêàæåì, ÷òî âûïîëíåíî óñëîâèå (2). Ïðåäïîëîæèì
ïðîòèâíîå, ò.å. íàéäåòñÿ òàêîé íîìåð j, ÷òî x 
j > 0 è
fj (x 
 [fj (x 
j   1) < max
l ).
j )   fj (x 
i + 1)   fi (x 
i )] = fl (x 
l + 1)   fl (x 
i  i  n
Çàìåòèì, ÷òî l = j, ïîñêîëüêó ïðè l = j íàðóøàëîñü óñëîâèå (1) äëÿ ôóíê-
öèè fj â òî÷êàõ x 
j . Îïðåäåëèì âåêòîð z :

 
x 
j   1, i = j,

zi =
x 
j + 1, i = l,
x 
i , i = j, l.
Ïîñëåäíåå íåðàâåíñòâî ìîæíî ïåðåïèñàòü â âèäå
fj (x 
l + 1).
j ) + fl (x 
l ) < fj (x 
j   1) + fl (x 
 fi (zi ), ÷òî ïðîòèâîðå÷èò îïðåäåëåíèþ x  .
Îòñþäà n
 fi (x 
i ) < n
i =1
i =1
Äîñòàòî÷íîñòü. Ïóñòü äëÿ ðàñïðåäåëåíèÿ ðåñóðñà x  âûïîëíåíî óñëîâèå
(2). Âîçüìåì ëþáîå ðàñïðåäåëåíèå x   M0 , x = x . Äîêàæåì, ÷òî
n
 n
 (3)
 fi (xi )  
 fi (x 
i ).
i =1
i =1
Ïîëîæèì
   = max
 [fi (x 
i )].
i + 1)   fi (x 
i  i  n
Ïîêàæåì, ÷òî ïðè âñåõ i âûïîëíåíî íåðàâåíñòâî
fi (x 
i   xi ). (4)
i )   fi (xi )    (x 
Ñêëàäûâàÿ íåðàâåíñòâà (4), ïîëó÷èì (3) è çàâåðøåíèå äîêàçàòåëüñòâà. Ðàñ-
ñìîòðèì äâà ñëó÷àÿ
1) x 
i   1)    . Ïîñêîëüêó
i > xi . Òîãäà x 
i > 0. Èç óñëîâèÿ (2) fi (x 
i )  fi (x 
ðàçíîñòè íå âîçðàñòàþò, ïîëó÷èì åùå íåðàâåíñòâà
fi (x 
i   2)    ,
i   1)   fi (x 
· · · · · ·
fi (x 
i   2)    .
i   1)   fi (x 
Âñåãî x 
i )  
i   xi íåðàâåíñòâ. Ñêëàäûâàÿ ýòè íåðàâåíñòâà, ïîëó÷èì fi (x 
fi (xi )    (x 
i   xi ).
 41

2) xi > x 
i )    . Ïîñêîëüêó
i . Ïî îïðåäåëåíèþ   èìååì fi (x 
i + 1)   fi (x 
ðàçíîñòè íå âîçðàñòàþò ïîëó÷èì åùå íåðàâåíñòâà
fi (x 
i + 1)    ,
i + 2)   fi (x 
· · · · · ·
fi (xi )   fi (xi   1)    .
Âñåãî xi   x 
i íåðàâåíñòâ. Ñêëàäûâàÿ ýòè íåðàâåíñòâà, ïîëó÷èì fi (xi )  
fi (x 
i ) èëè (4).
i )    (xi   x 
Óïðàæíåíèÿ. 1. Ñôîðìóëèðóéòå àíàëîãè òåîðåì 3.10 è 3.11 äëÿ íåïðå-
 n
 n
ðûâíîé è äèñêðåòíîé çàäà÷ íà ìèíèìóì min
 fi (xi ) è min
 fi (xi ).
x  M 0
x  M 0
i =1
i =1
2. Íà îñíîâå êðèòåðèÿ Ãðîññà ðàçðàáîòàéòå àëãîðèòì ðåøåíèÿ çàäà÷è
(II) . Äîêàæèòå, ÷òî ýòîò àëãîðèòì ñõîäèòñÿ çà êîíå÷íîå ÷èñëî øàãîâ.
42
�2礼�